home *** CD-ROM | disk | FTP | other *** search
/ Aminet 40 / Aminet 40 (2000)(Schatztruhe)[!][Dec 2000].iso / Aminet / dev / lang / Python16_Src.lha / Python16_Source / Modules / parsermodule.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-08-03  |  78.7 KB  |  2,693 lines
  1. /*  parsermodule.c
  2.  *
  3.  *  Copyright 1995-1996 by Fred L. Drake, Jr. and Virginia Polytechnic
  4.  *  Institute and State University, Blacksburg, Virginia, USA.
  5.  *  Portions copyright 1991-1995 by Stichting Mathematisch Centrum,
  6.  *  Amsterdam, The Netherlands.  Copying is permitted under the terms
  7.  *  associated with the main Python distribution, with the additional
  8.  *  restriction that this additional notice be included and maintained
  9.  *  on all distributed copies.
  10.  *
  11.  *  This module serves to replace the original parser module written
  12.  *  by Guido.  The functionality is not matched precisely, but the
  13.  *  original may be implemented on top of this.  This is desirable
  14.  *  since the source of the text to be parsed is now divorced from
  15.  *  this interface.
  16.  *
  17.  *  Unlike the prior interface, the ability to give a parse tree
  18.  *  produced by Python code as a tuple to the compiler is enabled by
  19.  *  this module.  See the documentation for more details.
  20.  *
  21.  *  I've added some annotations that help with the lint code-checking
  22.  *  program, but they're not complete by a long shot.  The real errors
  23.  *  that lint detects are gone, but there are still warnings with
  24.  *  Py_[X]DECREF() and Py_[X]INCREF() macros.  The lint annotations
  25.  *  look like "NOTE(...)".
  26.  */
  27.  
  28. #include "Python.h"                     /* general Python API             */
  29. #include "graminit.h"                   /* symbols defined in the grammar */
  30. #include "node.h"                       /* internal parser structure      */
  31. #include "token.h"                      /* token definitions              */
  32.                                         /* ISTERMINAL() / ISNONTERMINAL() */
  33. #include "compile.h"                    /* PyNode_Compile()               */
  34.  
  35. #ifdef lint
  36. #include <note.h>
  37. #else
  38. #define NOTE(x)
  39. #endif
  40.  
  41. #ifdef macintosh
  42. char *strdup(char *);
  43. #endif
  44.  
  45. /*  String constants used to initialize module attributes.
  46.  *
  47.  */
  48. static char*
  49. parser_copyright_string
  50. = "Copyright 1995-1996 by Virginia Polytechnic Institute & State\n\
  51. University, Blacksburg, Virginia, USA, and Fred L. Drake, Jr., Reston,\n\
  52. Virginia, USA.  Portions copyright 1991-1995 by Stichting Mathematisch\n\
  53. Centrum, Amsterdam, The Netherlands.";
  54.  
  55.  
  56. static char*
  57. parser_doc_string
  58. = "This is an interface to Python's internal parser.";
  59.  
  60. static char*
  61. parser_version_string = "0.4";
  62.  
  63.  
  64. typedef PyObject* (*SeqMaker) (int length);
  65. typedef int (*SeqInserter) (PyObject* sequence,
  66.                             int index,
  67.                             PyObject* element);
  68.  
  69. /*  The function below is copyrigthed by Stichting Mathematisch Centrum.  The
  70.  *  original copyright statement is included below, and continues to apply
  71.  *  in full to the function immediately following.  All other material is
  72.  *  original, copyrighted by Fred L. Drake, Jr. and Virginia Polytechnic
  73.  *  Institute and State University.  Changes were made to comply with the
  74.  *  new naming conventions.  Added arguments to provide support for creating
  75.  *  lists as well as tuples, and optionally including the line numbers.
  76.  */
  77.  
  78. static PyObject*
  79. node2tuple(node *n,                     /* node to convert               */
  80.            SeqMaker mkseq,              /* create sequence               */
  81.            SeqInserter addelem,         /* func. to add elem. in seq.    */
  82.            int lineno)                  /* include line numbers?         */
  83. {
  84.     if (n == NULL) {
  85.         Py_INCREF(Py_None);
  86.         return (Py_None);
  87.     }
  88.     if (ISNONTERMINAL(TYPE(n))) {
  89.         int i;
  90.         PyObject *v;
  91.         PyObject *w;
  92.  
  93.         v = mkseq(1 + NCH(n));
  94.         if (v == NULL)
  95.             return (v);
  96.         w = PyInt_FromLong(TYPE(n));
  97.         if (w == NULL) {
  98.             Py_DECREF(v);
  99.             return ((PyObject*) NULL);
  100.         }
  101.         (void) addelem(v, 0, w);
  102.         for (i = 0; i < NCH(n); i++) {
  103.             w = node2tuple(CHILD(n, i), mkseq, addelem, lineno);
  104.             if (w == NULL) {
  105.                 Py_DECREF(v);
  106.                 return ((PyObject*) NULL);
  107.             }
  108.             (void) addelem(v, i+1, w);
  109.         }
  110.         return (v);
  111.     }
  112.     else if (ISTERMINAL(TYPE(n))) {
  113.         PyObject *result = mkseq(2 + lineno);
  114.         if (result != NULL) {
  115.             (void) addelem(result, 0, PyInt_FromLong(TYPE(n)));
  116.             (void) addelem(result, 1, PyString_FromString(STR(n)));
  117.             if (lineno == 1)
  118.                 (void) addelem(result, 2, PyInt_FromLong(n->n_lineno));
  119.         }
  120.         return (result);
  121.     }
  122.     else {
  123.         PyErr_SetString(PyExc_SystemError,
  124.                         "unrecognized parse tree node type");
  125.         return ((PyObject*) NULL);
  126.     }
  127. }
  128. /*
  129.  *  End of material copyrighted by Stichting Mathematisch Centrum.
  130.  */
  131.  
  132.  
  133.  
  134. /*  There are two types of intermediate objects we're interested in:
  135.  *  'eval' and 'exec' types.  These constants can be used in the ast_type
  136.  *  field of the object type to identify which any given object represents.
  137.  *  These should probably go in an external header to allow other extensions
  138.  *  to use them, but then, we really should be using C++ too.  ;-)
  139.  *
  140.  *  The PyAST_FRAGMENT type is not currently supported.  Maybe not useful?
  141.  *  Haven't decided yet.
  142.  */
  143.  
  144. #define PyAST_EXPR      1
  145. #define PyAST_SUITE     2
  146. #define PyAST_FRAGMENT  3
  147.  
  148.  
  149. /*  These are the internal objects and definitions required to implement the
  150.  *  AST type.  Most of the internal names are more reminiscent of the 'old'
  151.  *  naming style, but the code uses the new naming convention.
  152.  */
  153.  
  154. static PyObject*
  155. parser_error = 0;
  156.  
  157.  
  158. typedef struct _PyAST_Object {
  159.     PyObject_HEAD                       /* standard object header           */
  160.     node* ast_node;                     /* the node* returned by the parser */
  161.     int   ast_type;                     /* EXPR or SUITE ?                  */
  162. } PyAST_Object;
  163.  
  164.  
  165. staticforward void
  166. parser_free(PyAST_Object *ast);
  167.  
  168. staticforward int
  169. parser_compare(PyAST_Object *left, PyAST_Object *right);
  170.  
  171. staticforward PyObject *
  172. parser_getattr(PyObject *self, char *name);
  173.  
  174.  
  175. static
  176. PyTypeObject PyAST_Type = {
  177.     PyObject_HEAD_INIT(NULL)
  178.     0,
  179.     "ast",                              /* tp_name              */
  180.     (int) sizeof(PyAST_Object),         /* tp_basicsize         */
  181.     0,                                  /* tp_itemsize          */
  182.     (destructor)parser_free,            /* tp_dealloc           */
  183.     0,                                  /* tp_print             */
  184.     parser_getattr,                     /* tp_getattr           */
  185.     0,                                  /* tp_setattr           */
  186.     (cmpfunc)parser_compare,            /* tp_compare           */
  187.     0,                                  /* tp_repr              */
  188.     0,                                  /* tp_as_number         */
  189.     0,                                  /* tp_as_sequence       */
  190.     0,                                  /* tp_as_mapping        */
  191.     0,                                  /* tp_hash              */
  192.     0,                                  /* tp_call              */
  193.     0,                                  /* tp_str               */
  194.     0,                                  /* tp_getattro          */
  195.     0,                                  /* tp_setattro          */
  196.  
  197.     /* Functions to access object as input/output buffer */
  198.     0,                                  /* tp_as_buffer         */
  199.  
  200.     Py_TPFLAGS_DEFAULT,                 /* tp_flags             */
  201.  
  202.     /* __doc__ */
  203.     "Intermediate representation of a Python parse tree."
  204. };  /* PyAST_Type */
  205.  
  206.  
  207. static int
  208. parser_compare_nodes(node *left, node *right)
  209. {
  210.     int j;
  211.  
  212.     if (TYPE(left) < TYPE(right))
  213.         return (-1);
  214.  
  215.     if (TYPE(right) < TYPE(left))
  216.         return (1);
  217.  
  218.     if (ISTERMINAL(TYPE(left)))
  219.         return (strcmp(STR(left), STR(right)));
  220.  
  221.     if (NCH(left) < NCH(right))
  222.         return (-1);
  223.  
  224.     if (NCH(right) < NCH(left))
  225.         return (1);
  226.  
  227.     for (j = 0; j < NCH(left); ++j) {
  228.         int v = parser_compare_nodes(CHILD(left, j), CHILD(right, j));
  229.  
  230.         if (v != 0)
  231.             return (v);
  232.     }
  233.     return (0);
  234. }
  235.  
  236.  
  237. /*  int parser_compare(PyAST_Object* left, PyAST_Object* right)
  238.  *
  239.  *  Comparison function used by the Python operators ==, !=, <, >, <=, >=
  240.  *  This really just wraps a call to parser_compare_nodes() with some easy
  241.  *  checks and protection code.
  242.  *
  243.  */
  244. static int
  245. parser_compare(PyAST_Object *left, PyAST_Object *right)
  246. {
  247.     if (left == right)
  248.         return (0);
  249.  
  250.     if ((left == 0) || (right == 0))
  251.         return (-1);
  252.  
  253.     return (parser_compare_nodes(left->ast_node, right->ast_node));
  254. }
  255.  
  256.  
  257. /*  parser_newastobject(node* ast)
  258.  *
  259.  *  Allocates a new Python object representing an AST.  This is simply the
  260.  *  'wrapper' object that holds a node* and allows it to be passed around in
  261.  *  Python code.
  262.  *
  263.  */
  264. static PyObject*
  265. parser_newastobject(node *ast, int type)
  266. {
  267.     PyAST_Object* o = PyObject_New(PyAST_Object, &PyAST_Type);
  268.  
  269.     if (o != 0) {
  270.         o->ast_node = ast;
  271.         o->ast_type = type;
  272.     }
  273.     else {
  274.         PyNode_Free(ast);
  275.     }
  276.     return ((PyObject*)o);
  277. }
  278.  
  279.  
  280. /*  void parser_free(PyAST_Object* ast)
  281.  *
  282.  *  This is called by a del statement that reduces the reference count to 0.
  283.  *
  284.  */
  285. static void
  286. parser_free(PyAST_Object *ast)
  287. {
  288.     PyNode_Free(ast->ast_node);
  289.     PyObject_Del(ast);
  290. }
  291.  
  292.  
  293. /*  parser_ast2tuple(PyObject* self, PyObject* args, PyObject* kw)
  294.  *
  295.  *  This provides conversion from a node* to a tuple object that can be
  296.  *  returned to the Python-level caller.  The AST object is not modified.
  297.  *
  298.  */
  299. static PyObject*
  300. parser_ast2tuple(PyAST_Object *self, PyObject *args, PyObject *kw)
  301. {
  302.     PyObject *line_option = 0;
  303.     PyObject *res = 0;
  304.     int ok;
  305.  
  306.     static char *keywords[] = {"ast", "line_info", NULL};
  307.  
  308.     if (self == NULL) {
  309.         ok = PyArg_ParseTupleAndKeywords(args, kw, "O!|O:ast2tuple", keywords,
  310.                                          &PyAST_Type, &self, &line_option);
  311.     }
  312.     else
  313.         ok = PyArg_ParseTupleAndKeywords(args, kw, "|O:totuple", &keywords[1],
  314.                                          &line_option);
  315.     if (ok != 0) {
  316.         int lineno = 0;
  317.         if (line_option != NULL) {
  318.             lineno = (PyObject_IsTrue(line_option) != 0) ? 1 : 0;
  319.         }
  320.         /*
  321.          *  Convert AST into a tuple representation.  Use Guido's function,
  322.          *  since it's known to work already.
  323.          */
  324.         res = node2tuple(((PyAST_Object*)self)->ast_node,
  325.                          PyTuple_New, PyTuple_SetItem, lineno);
  326.     }
  327.     return (res);
  328. }
  329.  
  330.  
  331. /*  parser_ast2list(PyObject* self, PyObject* args, PyObject* kw)
  332.  *
  333.  *  This provides conversion from a node* to a list object that can be
  334.  *  returned to the Python-level caller.  The AST object is not modified.
  335.  *
  336.  */
  337. static PyObject*
  338. parser_ast2list(PyAST_Object *self, PyObject *args, PyObject *kw)
  339. {
  340.     PyObject *line_option = 0;
  341.     PyObject *res = 0;
  342.     int ok;
  343.  
  344.     static char *keywords[] = {"ast", "line_info", NULL};
  345.  
  346.     if (self == NULL)
  347.         ok = PyArg_ParseTupleAndKeywords(args, kw, "O!|O:ast2list", keywords,
  348.                                          &PyAST_Type, &self, &line_option);
  349.     else
  350.         ok = PyArg_ParseTupleAndKeywords(args, kw, "|O:tolist", &keywords[1],
  351.                                          &line_option);
  352.     if (ok) {
  353.         int lineno = 0;
  354.         if (line_option != 0) {
  355.             lineno = PyObject_IsTrue(line_option) ? 1 : 0;
  356.         }
  357.         /*
  358.          *  Convert AST into a tuple representation.  Use Guido's function,
  359.          *  since it's known to work already.
  360.          */
  361.         res = node2tuple(self->ast_node,
  362.                          PyList_New, PyList_SetItem, lineno);
  363.     }
  364.     return (res);
  365. }
  366.  
  367.  
  368. /*  parser_compileast(PyObject* self, PyObject* args)
  369.  *
  370.  *  This function creates code objects from the parse tree represented by
  371.  *  the passed-in data object.  An optional file name is passed in as well.
  372.  *
  373.  */
  374. static PyObject*
  375. parser_compileast(PyAST_Object *self, PyObject *args, PyObject *kw)
  376. {
  377.     PyObject*     res = 0;
  378.     char*         str = "<ast>";
  379.     int ok;
  380.  
  381.     static char *keywords[] = {"ast", "filename", NULL};
  382.  
  383.     if (self == NULL)
  384.         ok = PyArg_ParseTupleAndKeywords(args, kw, "O!|s:compileast", keywords,
  385.                                          &PyAST_Type, &self, &str);
  386.     else
  387.         ok = PyArg_ParseTupleAndKeywords(args, kw, "|s:compile", &keywords[1],
  388.                                          &str);
  389.  
  390.     if (ok)
  391.         res = (PyObject *)PyNode_Compile(self->ast_node, str);
  392.  
  393.     return (res);
  394. }
  395.  
  396.  
  397. /*  PyObject* parser_isexpr(PyObject* self, PyObject* args)
  398.  *  PyObject* parser_issuite(PyObject* self, PyObject* args)
  399.  *
  400.  *  Checks the passed-in AST object to determine if it is an expression or
  401.  *  a statement suite, respectively.  The return is a Python truth value.
  402.  *
  403.  */
  404. static PyObject*
  405. parser_isexpr(PyAST_Object *self, PyObject *args, PyObject *kw)
  406. {
  407.     PyObject* res = 0;
  408.     int ok;
  409.  
  410.     static char *keywords[] = {"ast", NULL};
  411.  
  412.     if (self == NULL)
  413.         ok = PyArg_ParseTupleAndKeywords(args, kw, "O!:isexpr", keywords,
  414.                                          &PyAST_Type, &self);
  415.     else
  416.         ok = PyArg_ParseTupleAndKeywords(args, kw, ":isexpr", &keywords[1]);
  417.  
  418.     if (ok) {
  419.         /* Check to see if the AST represents an expression or not. */
  420.         res = (self->ast_type == PyAST_EXPR) ? Py_True : Py_False;
  421.         Py_INCREF(res);
  422.     }
  423.     return (res);
  424. }
  425.  
  426.  
  427. static PyObject*
  428. parser_issuite(PyAST_Object *self, PyObject *args, PyObject *kw)
  429. {
  430.     PyObject* res = 0;
  431.     int ok;
  432.  
  433.     static char *keywords[] = {"ast", NULL};
  434.  
  435.     if (self == NULL)
  436.         ok = PyArg_ParseTupleAndKeywords(args, kw, "O!:issuite", keywords,
  437.                                          &PyAST_Type, &self);
  438.     else
  439.         ok = PyArg_ParseTupleAndKeywords(args, kw, ":issuite", &keywords[1]);
  440.  
  441.     if (ok) {
  442.         /* Check to see if the AST represents an expression or not. */
  443.         res = (self->ast_type == PyAST_EXPR) ? Py_False : Py_True;
  444.         Py_INCREF(res);
  445.     }
  446.     return (res);
  447. }
  448.  
  449.  
  450. #define PUBLIC_METHOD_TYPE (METH_VARARGS|METH_KEYWORDS)
  451.  
  452. static PyMethodDef
  453. parser_methods[] = {
  454.     {"compile",         (PyCFunction)parser_compileast, PUBLIC_METHOD_TYPE,
  455.         "Compile this AST object into a code object."},
  456.     {"isexpr",          (PyCFunction)parser_isexpr,     PUBLIC_METHOD_TYPE,
  457.         "Determines if this AST object was created from an expression."},
  458.     {"issuite",         (PyCFunction)parser_issuite,    PUBLIC_METHOD_TYPE,
  459.         "Determines if this AST object was created from a suite."},
  460.     {"tolist",          (PyCFunction)parser_ast2list,   PUBLIC_METHOD_TYPE,
  461.         "Creates a list-tree representation of this AST."},
  462.     {"totuple",         (PyCFunction)parser_ast2tuple,  PUBLIC_METHOD_TYPE,
  463.         "Creates a tuple-tree representation of this AST."},
  464.  
  465.     {NULL, NULL, 0, NULL}
  466. };
  467.  
  468.  
  469. static PyObject*
  470. parser_getattr(self, name)
  471.      PyObject *self;
  472.      char *name;
  473. {
  474.     return (Py_FindMethod(parser_methods, self, name));
  475. }
  476.  
  477.  
  478. /*  err_string(char* message)
  479.  *
  480.  *  Sets the error string for an exception of type ParserError.
  481.  *
  482.  */
  483. static void
  484. err_string(message)
  485.      char *message;
  486. {
  487.     PyErr_SetString(parser_error, message);
  488. }
  489.  
  490.  
  491. /*  PyObject* parser_do_parse(PyObject* args, int type)
  492.  *
  493.  *  Internal function to actually execute the parse and return the result if
  494.  *  successful, or set an exception if not.
  495.  *
  496.  */
  497. static PyObject*
  498. parser_do_parse(PyObject *args, PyObject *kw, char *argspec, int type)
  499. {
  500.     char*     string = 0;
  501.     PyObject* res    = 0;
  502.  
  503.     static char *keywords[] = {"source", NULL};
  504.  
  505.     if (PyArg_ParseTupleAndKeywords(args, kw, argspec, keywords, &string)) {
  506.         node* n = PyParser_SimpleParseString(string,
  507.                                              (type == PyAST_EXPR)
  508.                                              ? eval_input : file_input);
  509.  
  510.         if (n != 0)
  511.             res = parser_newastobject(n, type);
  512.         else
  513.             err_string("Could not parse string.");
  514.     }
  515.     return (res);
  516. }
  517.  
  518.  
  519. /*  PyObject* parser_expr(PyObject* self, PyObject* args)
  520.  *  PyObject* parser_suite(PyObject* self, PyObject* args)
  521.  *
  522.  *  External interfaces to the parser itself.  Which is called determines if
  523.  *  the parser attempts to recognize an expression ('eval' form) or statement
  524.  *  suite ('exec' form).  The real work is done by parser_do_parse() above.
  525.  *
  526.  */
  527. static PyObject*
  528. parser_expr(PyAST_Object *self, PyObject *args, PyObject *kw)
  529. {
  530.     NOTE(ARGUNUSED(self))
  531.     return (parser_do_parse(args, kw, "s:expr", PyAST_EXPR));
  532. }
  533.  
  534.  
  535. static PyObject*
  536. parser_suite(PyAST_Object *self, PyObject *args, PyObject *kw)
  537. {
  538.     NOTE(ARGUNUSED(self))
  539.     return (parser_do_parse(args, kw, "s:suite", PyAST_SUITE));
  540. }
  541.  
  542.  
  543.  
  544. /*  This is the messy part of the code.  Conversion from a tuple to an AST
  545.  *  object requires that the input tuple be valid without having to rely on
  546.  *  catching an exception from the compiler.  This is done to allow the
  547.  *  compiler itself to remain fast, since most of its input will come from
  548.  *  the parser directly, and therefore be known to be syntactically correct.
  549.  *  This validation is done to ensure that we don't core dump the compile
  550.  *  phase, returning an exception instead.
  551.  *
  552.  *  Two aspects can be broken out in this code:  creating a node tree from
  553.  *  the tuple passed in, and verifying that it is indeed valid.  It may be
  554.  *  advantageous to expand the number of AST types to include funcdefs and
  555.  *  lambdadefs to take advantage of the optimizer, recognizing those ASTs
  556.  *  here.  They are not necessary, and not quite as useful in a raw form.
  557.  *  For now, let's get expressions and suites working reliably.
  558.  */
  559.  
  560.  
  561. staticforward node* build_node_tree(PyObject *tuple);
  562. staticforward int   validate_expr_tree(node *tree);
  563. staticforward int   validate_file_input(node *tree);
  564.  
  565.  
  566. /*  PyObject* parser_tuple2ast(PyObject* self, PyObject* args)
  567.  *
  568.  *  This is the public function, called from the Python code.  It receives a
  569.  *  single tuple object from the caller, and creates an AST object if the
  570.  *  tuple can be validated.  It does this by checking the first code of the
  571.  *  tuple, and, if acceptable, builds the internal representation.  If this
  572.  *  step succeeds, the internal representation is validated as fully as
  573.  *  possible with the various validate_*() routines defined below.
  574.  *
  575.  *  This function must be changed if support is to be added for PyAST_FRAGMENT
  576.  *  AST objects.
  577.  *
  578.  */
  579. static PyObject*
  580. parser_tuple2ast(PyAST_Object *self, PyObject *args, PyObject *kw)
  581. {
  582.     NOTE(ARGUNUSED(self))
  583.     PyObject *ast = 0;
  584.     PyObject *tuple = 0;
  585.     PyObject *temp = 0;
  586.     int ok;
  587.     int start_sym = 0;
  588.  
  589.     static char *keywords[] = {"sequence", NULL};
  590.  
  591.     if (!PyArg_ParseTupleAndKeywords(args, kw, "O:tuple2ast", keywords,
  592.                                      &tuple))
  593.         return (0);
  594.     if (!PySequence_Check(tuple)) {
  595.         PyErr_SetString(PyExc_ValueError,
  596.                         "tuple2ast() requires a single sequence argument");
  597.         return (0);
  598.     }
  599.     /*
  600.      *  This mess of tests is written this way so we can use the abstract
  601.      *  object interface (AOI).  Unfortunately, the AOI increments reference
  602.      *  counts, which requires that we store a pointer to retrieved object
  603.      *  so we can DECREF it after the check.  But we really should accept
  604.      *  lists as well as tuples at the very least.
  605.      */
  606.     ok = PyObject_Length(tuple) >= 2;
  607.     if (ok) {
  608.         temp = PySequence_GetItem(tuple, 0);
  609.         ok = (temp != NULL) && PyInt_Check(temp);
  610.         if (ok)
  611.             /* this is used after the initial checks: */
  612.             start_sym = PyInt_AS_LONG(temp);
  613.         Py_XDECREF(temp);
  614.     }
  615.     if (ok) {
  616.         temp = PySequence_GetItem(tuple, 1);
  617.         ok = (temp != NULL) && PySequence_Check(temp);
  618.         Py_XDECREF(temp);
  619.     }
  620.     if (ok) {
  621.         temp = PySequence_GetItem(tuple, 1);
  622.         ok = (temp != NULL) && PyObject_Length(temp) >= 2;
  623.         if (ok) {
  624.             PyObject *temp2 = PySequence_GetItem(temp, 0);
  625.             if (temp2 != NULL) {
  626.                 ok = PyInt_Check(temp2);
  627.                 Py_DECREF(temp2);
  628.             }
  629.         }
  630.         Py_XDECREF(temp);
  631.     }
  632.     /* If we've failed at some point, get out of here. */
  633.     if (!ok) {
  634.         err_string("malformed sequence for tuple2ast()");
  635.         return (0);
  636.     }
  637.     /*
  638.      *  This might be a valid parse tree, but let's do a quick check
  639.      *  before we jump the gun.
  640.      */
  641.     if (start_sym == eval_input) {
  642.         /*  Might be an eval form.  */
  643.         node* expression = build_node_tree(tuple);
  644.  
  645.         if ((expression != 0) && validate_expr_tree(expression))
  646.             ast = parser_newastobject(expression, PyAST_EXPR);
  647.     }
  648.     else if (start_sym == file_input) {
  649.         /*  This looks like an exec form so far.  */
  650.         node* suite_tree = build_node_tree(tuple);
  651.  
  652.         if ((suite_tree != 0) && validate_file_input(suite_tree))
  653.             ast = parser_newastobject(suite_tree, PyAST_SUITE);
  654.     }
  655.     else
  656.         /*  This is a fragment, and is not yet supported.  Maybe they
  657.          *  will be if I find a use for them.
  658.          */
  659.         err_string("Fragmentary parse trees not supported.");
  660.  
  661.     /*  Make sure we throw an exception on all errors.  We should never
  662.      *  get this, but we'd do well to be sure something is done.
  663.      */
  664.     if ((ast == 0) && !PyErr_Occurred())
  665.         err_string("Unspecified ast error occurred.");
  666.  
  667.     return (ast);
  668. }
  669.  
  670.  
  671. /*  int check_terminal_tuple()
  672.  *
  673.  *  Check a tuple to determine that it is indeed a valid terminal
  674.  *  node.  The node is known to be required as a terminal, so we throw
  675.  *  an exception if there is a failure.
  676.  *
  677.  *  The format of an acceptable terminal tuple is "(is[i])": the fact
  678.  *  that elem is a tuple and the integer is a valid terminal symbol
  679.  *  has been established before this function is called.  We must
  680.  *  check the length of the tuple and the type of the second element
  681.  *  and optional third element.  We do *NOT* check the actual text of
  682.  *  the string element, which we could do in many cases.  This is done
  683.  *  by the validate_*() functions which operate on the internal
  684.  *  representation.
  685.  */
  686. static int
  687. check_terminal_tuple(PyObject *elem)
  688. {
  689.     int   len = PyObject_Length(elem);
  690.     int   res = 1;
  691.     char* str = "Illegal terminal symbol; bad node length.";
  692.  
  693.     if ((len == 2) || (len == 3)) {
  694.         PyObject *temp = PySequence_GetItem(elem, 1);
  695.         res = PyString_Check(temp);
  696.         str = "Illegal terminal symbol; expected a string.";
  697.         if (res && (len == 3)) {
  698.             PyObject* third = PySequence_GetItem(elem, 2);
  699.             res = PyInt_Check(third);
  700.             str = "Invalid third element of terminal node.";
  701.             Py_XDECREF(third);
  702.         }
  703.         Py_XDECREF(temp);
  704.     }
  705.     else {
  706.         res = 0;
  707.     }
  708.     if (!res) {
  709.         elem = Py_BuildValue("(os)", elem, str);
  710.         PyErr_SetObject(parser_error, elem);
  711.     }
  712.     return (res);
  713. }
  714.  
  715.  
  716. /*  node* build_node_children()
  717.  *
  718.  *  Iterate across the children of the current non-terminal node and build
  719.  *  their structures.  If successful, return the root of this portion of
  720.  *  the tree, otherwise, 0.  Any required exception will be specified already,
  721.  *  and no memory will have been deallocated.
  722.  *
  723.  */
  724. static node*
  725. build_node_children(PyObject *tuple, node *root, int *line_num)
  726. {
  727.     int len = PyObject_Length(tuple);
  728.     int i;
  729.  
  730.     for (i = 1; i < len; ++i) {
  731.         /* elem must always be a tuple, however simple */
  732.         PyObject* elem = PySequence_GetItem(tuple, i);
  733.         int ok = elem != NULL;
  734.         long  type = 0;
  735.         char *strn = 0;
  736.  
  737.         if (ok)
  738.             ok = PySequence_Check(elem);
  739.         if (ok) {
  740.             PyObject *temp = PySequence_GetItem(elem, 0);
  741.             if (temp == NULL)
  742.                 ok = 0;
  743.             else {
  744.                 ok = PyInt_Check(temp);
  745.                 if (ok)
  746.                     type = PyInt_AS_LONG(temp);
  747.                 Py_DECREF(temp);
  748.             }
  749.         }
  750.         if (!ok) {
  751.             PyErr_SetObject(parser_error,
  752.                             Py_BuildValue("(os)", elem,
  753.                                           "Illegal node construct."));
  754.             Py_XDECREF(elem);
  755.             return (0);
  756.         }
  757.         if (ISTERMINAL(type)) {
  758.             if (check_terminal_tuple(elem)) {
  759.                 PyObject *temp = PySequence_GetItem(elem, 1);
  760.  
  761.                 /* check_terminal_tuple() already verified it's a string */
  762.                 strn = (char *)PyMem_MALLOC(PyString_GET_SIZE(temp) + 1);
  763.                 if (strn != NULL)
  764.                     (void) strcpy(strn, PyString_AS_STRING(temp));
  765.                 Py_DECREF(temp);
  766.  
  767.                 if (PyObject_Length(elem) == 3) {
  768.                     PyObject* temp = PySequence_GetItem(elem, 2);
  769.                     *line_num = PyInt_AsLong(temp);
  770.                     Py_DECREF(temp);
  771.                 }
  772.             }
  773.             else {
  774.                 Py_XDECREF(elem);
  775.                 return (0);
  776.             }
  777.         }
  778.         else if (!ISNONTERMINAL(type)) {
  779.             /*
  780.              *  It has to be one or the other; this is an error.
  781.              *  Throw an exception.
  782.              */
  783.             PyErr_SetObject(parser_error,
  784.                             Py_BuildValue("(os)", elem,
  785.                                           "Unknown node type."));
  786.             Py_XDECREF(elem);
  787.             return (0);
  788.         }
  789.         PyNode_AddChild(root, type, strn, *line_num);
  790.  
  791.         if (ISNONTERMINAL(type)) {
  792.             node* new_child = CHILD(root, i - 1);
  793.  
  794.             if (new_child != build_node_children(elem, new_child, line_num)) {
  795.                 Py_XDECREF(elem);
  796.                 return (0);
  797.             }
  798.         }
  799.         else if (type == NEWLINE) {     /* It's true:  we increment the     */
  800.             ++(*line_num);              /* line number *after* the newline! */
  801.         }
  802.         Py_XDECREF(elem);
  803.     }
  804.     return (root);
  805. }
  806.  
  807.  
  808. static node*
  809. build_node_tree(PyObject *tuple)
  810. {
  811.     node* res = 0;
  812.     PyObject *temp = PySequence_GetItem(tuple, 0);
  813.     long  num = -1;
  814.  
  815.     if (temp != NULL)
  816.         num = PyInt_AsLong(temp);
  817.     Py_XDECREF(temp);
  818.     if (ISTERMINAL(num)) {
  819.         /*
  820.          *  The tuple is simple, but it doesn't start with a start symbol.
  821.          *  Throw an exception now and be done with it.
  822.          */
  823.         tuple = Py_BuildValue("(os)", tuple,
  824.                     "Illegal ast tuple; cannot start with terminal symbol.");
  825.         PyErr_SetObject(parser_error, tuple);
  826.     }
  827.     else if (ISNONTERMINAL(num)) {
  828.         /*
  829.          *  Not efficient, but that can be handled later.
  830.          */
  831.         int line_num = 0;
  832.  
  833.         res = PyNode_New(num);
  834.         if (res != build_node_children(tuple, res, &line_num)) {
  835.             PyNode_Free(res);
  836.             res = 0;
  837.         }
  838.     }
  839.     else
  840.         /*  The tuple is illegal -- if the number is neither TERMINAL nor
  841.          *  NONTERMINAL, we can't use it.
  842.          */
  843.         PyErr_SetObject(parser_error,
  844.                         Py_BuildValue("(os)", tuple,
  845.                                       "Illegal component tuple."));
  846.  
  847.     return (res);
  848. }
  849.  
  850.  
  851. #ifdef HAVE_OLD_CPP
  852. #define VALIDATER(n)    static int validate_/**/n(node *tree)
  853. #else
  854. #define VALIDATER(n)    static int validate_##n(node *tree)
  855. #endif
  856.  
  857.  
  858. /*
  859.  *  Validation routines used within the validation section:
  860.  */
  861. staticforward int validate_terminal(node *terminal, int type, char *string);
  862.  
  863. #define validate_ampersand(ch)  validate_terminal(ch,      AMPER, "&")
  864. #define validate_circumflex(ch) validate_terminal(ch, CIRCUMFLEX, "^")
  865. #define validate_colon(ch)      validate_terminal(ch,      COLON, ":")
  866. #define validate_comma(ch)      validate_terminal(ch,      COMMA, ",")
  867. #define validate_dedent(ch)     validate_terminal(ch,     DEDENT, "")
  868. #define validate_equal(ch)      validate_terminal(ch,      EQUAL, "=")
  869. #define validate_indent(ch)     validate_terminal(ch,     INDENT, (char*)NULL)
  870. #define validate_lparen(ch)     validate_terminal(ch,       LPAR, "(")
  871. #define validate_newline(ch)    validate_terminal(ch,    NEWLINE, (char*)NULL)
  872. #define validate_rparen(ch)     validate_terminal(ch,       RPAR, ")")
  873. #define validate_semi(ch)       validate_terminal(ch,       SEMI, ";")
  874. #define validate_star(ch)       validate_terminal(ch,       STAR, "*")
  875. #define validate_vbar(ch)       validate_terminal(ch,       VBAR, "|")
  876. #define validate_doublestar(ch) validate_terminal(ch, DOUBLESTAR, "**")
  877. #define validate_dot(ch)        validate_terminal(ch,        DOT, ".")
  878. #define validate_name(ch, str)  validate_terminal(ch,       NAME, str)
  879.  
  880. VALIDATER(node);                VALIDATER(small_stmt);
  881. VALIDATER(class);               VALIDATER(node);
  882. VALIDATER(parameters);          VALIDATER(suite);
  883. VALIDATER(testlist);            VALIDATER(varargslist);
  884. VALIDATER(fpdef);               VALIDATER(fplist);
  885. VALIDATER(stmt);                VALIDATER(simple_stmt);
  886. VALIDATER(expr_stmt);           VALIDATER(power);
  887. VALIDATER(print_stmt);          VALIDATER(del_stmt);
  888. VALIDATER(return_stmt);
  889. VALIDATER(raise_stmt);          VALIDATER(import_stmt);
  890. VALIDATER(global_stmt);
  891. VALIDATER(assert_stmt);
  892. VALIDATER(exec_stmt);           VALIDATER(compound_stmt);
  893. VALIDATER(while);               VALIDATER(for);
  894. VALIDATER(try);                 VALIDATER(except_clause);
  895. VALIDATER(test);                VALIDATER(and_test);
  896. VALIDATER(not_test);            VALIDATER(comparison);
  897. VALIDATER(comp_op);             VALIDATER(expr);
  898. VALIDATER(xor_expr);            VALIDATER(and_expr);
  899. VALIDATER(shift_expr);          VALIDATER(arith_expr);
  900. VALIDATER(term);                VALIDATER(factor);
  901. VALIDATER(atom);                VALIDATER(lambdef);
  902. VALIDATER(trailer);             VALIDATER(subscript);
  903. VALIDATER(subscriptlist);       VALIDATER(sliceop);
  904. VALIDATER(exprlist);            VALIDATER(dictmaker);
  905. VALIDATER(arglist);             VALIDATER(argument);
  906.  
  907.  
  908. #define is_even(n)      (((n) & 1) == 0)
  909. #define is_odd(n)       (((n) & 1) == 1)
  910.  
  911.  
  912. static int
  913. validate_ntype(node *n, int t)
  914. {
  915.     int res = (TYPE(n) == t);
  916.  
  917.     if (!res) {
  918.         char buffer[128];
  919.         (void) sprintf(buffer, "Expected node type %d, got %d.", t, TYPE(n));
  920.         err_string(buffer);
  921.     }
  922.     return (res);
  923. }
  924.  
  925.  
  926. /*  Verifies that the number of child nodes is exactly 'num', raising
  927.  *  an exception if it isn't.  The exception message does not indicate
  928.  *  the exact number of nodes, allowing this to be used to raise the
  929.  *  "right" exception when the wrong number of nodes is present in a
  930.  *  specific variant of a statement's syntax.  This is commonly used
  931.  *  in that fashion.
  932.  */
  933. static int
  934. validate_numnodes(node *n, int num, const char *const name)
  935. {
  936.     if (NCH(n) != num) {
  937.         char buff[60];
  938.         (void) sprintf(buff, "Illegal number of children for %s node.", name);
  939.         err_string(buff);
  940.     }
  941.     return (NCH(n) == num);
  942. }
  943.  
  944.  
  945. static int
  946. validate_terminal(node *terminal, int type, char *string)
  947. {
  948.     int res = (validate_ntype(terminal, type)
  949.                && ((string == 0) || (strcmp(string, STR(terminal)) == 0)));
  950.  
  951.     if (!res && !PyErr_Occurred()) {
  952.         char buffer[60];
  953.         (void) sprintf(buffer, "Illegal terminal: expected \"%s\"", string);
  954.         err_string(buffer);
  955.     }
  956.     return (res);
  957. }
  958.  
  959.  
  960. /*  X (',' X) [',']
  961.  */
  962. static int
  963. validate_repeating_list(node *tree, int ntype, int (*vfunc)(),
  964.                         const char *const name)
  965. {
  966.     int nch = NCH(tree);
  967.     int res = (nch && validate_ntype(tree, ntype)
  968.                && vfunc(CHILD(tree, 0)));
  969.  
  970.     if (!res && !PyErr_Occurred())
  971.         (void) validate_numnodes(tree, 1, name);
  972.     else {
  973.         if (is_even(nch))
  974.             res = validate_comma(CHILD(tree, --nch));
  975.         if (res && nch > 1) {
  976.             int pos = 1;
  977.             for ( ; res && pos < nch; pos += 2)
  978.                 res = (validate_comma(CHILD(tree, pos))
  979.                        && vfunc(CHILD(tree, pos + 1)));
  980.         }
  981.     }
  982.     return (res);
  983. }
  984.  
  985.  
  986. /*  VALIDATE(class)
  987.  *
  988.  *  classdef:
  989.  *      'class' NAME ['(' testlist ')'] ':' suite
  990.  */
  991. static int
  992. validate_class(node *tree)
  993. {
  994.     int nch = NCH(tree);
  995.     int res = validate_ntype(tree, classdef) && ((nch == 4) || (nch == 7));
  996.  
  997.     if (res) {
  998.         res = (validate_name(CHILD(tree, 0), "class")
  999.                && validate_ntype(CHILD(tree, 1), NAME)
  1000.                && validate_colon(CHILD(tree, nch - 2))
  1001.                && validate_suite(CHILD(tree, nch - 1)));
  1002.     }
  1003.     else
  1004.         (void) validate_numnodes(tree, 4, "class");
  1005.     if (res && (nch == 7)) {
  1006.         res = (validate_lparen(CHILD(tree, 2))
  1007.                && validate_testlist(CHILD(tree, 3))
  1008.                && validate_rparen(CHILD(tree, 4)));
  1009.     }
  1010.     return (res);
  1011. }
  1012.  
  1013.  
  1014. /*  if_stmt:
  1015.  *      'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]
  1016.  */
  1017. static int
  1018. validate_if(node *tree)
  1019. {
  1020.     int nch = NCH(tree);
  1021.     int res = (validate_ntype(tree, if_stmt)
  1022.                && (nch >= 4)
  1023.                && validate_name(CHILD(tree, 0), "if")
  1024.                && validate_test(CHILD(tree, 1))
  1025.                && validate_colon(CHILD(tree, 2))
  1026.                && validate_suite(CHILD(tree, 3)));
  1027.  
  1028.     if (res && ((nch % 4) == 3)) {
  1029.         /*  ... 'else' ':' suite  */
  1030.         res = (validate_name(CHILD(tree, nch - 3), "else")
  1031.                && validate_colon(CHILD(tree, nch - 2))
  1032.                && validate_suite(CHILD(tree, nch - 1)));
  1033.         nch -= 3;
  1034.     }
  1035.     else if (!res && !PyErr_Occurred())
  1036.         (void) validate_numnodes(tree, 4, "if");
  1037.     if ((nch % 4) != 0)
  1038.         /* Will catch the case for nch < 4 */
  1039.         res = validate_numnodes(tree, 0, "if");
  1040.     else if (res && (nch > 4)) {
  1041.         /*  ... ('elif' test ':' suite)+ ...  */
  1042.         int j = 4;
  1043.         while ((j < nch) && res) {
  1044.             res = (validate_name(CHILD(tree, j), "elif")
  1045.                    && validate_colon(CHILD(tree, j + 2))
  1046.                    && validate_test(CHILD(tree, j + 1))
  1047.                    && validate_suite(CHILD(tree, j + 3)));
  1048.             j += 4;
  1049.         }
  1050.     }
  1051.     return (res);
  1052. }
  1053.  
  1054.  
  1055. /*  parameters:
  1056.  *      '(' [varargslist] ')'
  1057.  *
  1058.  */
  1059. static int
  1060. validate_parameters(node *tree)
  1061. {
  1062.     int nch = NCH(tree);
  1063.     int res = validate_ntype(tree, parameters) && ((nch == 2) || (nch == 3));
  1064.  
  1065.     if (res) {
  1066.         res = (validate_lparen(CHILD(tree, 0))
  1067.                && validate_rparen(CHILD(tree, nch - 1)));
  1068.         if (res && (nch == 3))
  1069.             res = validate_varargslist(CHILD(tree, 1));
  1070.     }
  1071.     else {
  1072.         (void) validate_numnodes(tree, 2, "parameters");
  1073.     }
  1074.     return (res);
  1075. }
  1076.  
  1077.  
  1078. /*  VALIDATE(suite)
  1079.  *
  1080.  *  suite:
  1081.  *      simple_stmt
  1082.  *    | NEWLINE INDENT stmt+ DEDENT
  1083.  */
  1084. static int
  1085. validate_suite(node *tree)
  1086. {
  1087.     int nch = NCH(tree);
  1088.     int res = (validate_ntype(tree, suite) && ((nch == 1) || (nch >= 4)));
  1089.  
  1090.     if (res && (nch == 1))
  1091.         res = validate_simple_stmt(CHILD(tree, 0));
  1092.     else if (res) {
  1093.         /*  NEWLINE INDENT stmt+ DEDENT  */
  1094.         res = (validate_newline(CHILD(tree, 0))
  1095.                && validate_indent(CHILD(tree, 1))
  1096.                && validate_stmt(CHILD(tree, 2))
  1097.                && validate_dedent(CHILD(tree, nch - 1)));
  1098.  
  1099.         if (res && (nch > 4)) {
  1100.             int i = 3;
  1101.             --nch;                      /* forget the DEDENT     */
  1102.             for ( ; res && (i < nch); ++i)
  1103.                 res = validate_stmt(CHILD(tree, i));
  1104.         }
  1105.         else if (nch < 4)
  1106.             res = validate_numnodes(tree, 4, "suite");
  1107.     }
  1108.     return (res);
  1109. }
  1110.  
  1111.  
  1112. static int
  1113. validate_testlist(node *tree)
  1114. {
  1115.     return (validate_repeating_list(tree, testlist,
  1116.                                     validate_test, "testlist"));
  1117. }
  1118.  
  1119.  
  1120. /*  VALIDATE(varargslist)
  1121.  *
  1122.  *  varargslist:
  1123.  *      (fpdef ['=' test] ',')* ('*' NAME [',' '*' '*' NAME] | '*' '*' NAME)
  1124.  *    | fpdef ['=' test] (',' fpdef ['=' test])* [',']
  1125.  *
  1126.  *      (fpdef ['=' test] ',')*
  1127.  *           ('*' NAME [',' ('**'|'*' '*') NAME]
  1128.  *         | ('**'|'*' '*') NAME)
  1129.  *    | fpdef ['=' test] (',' fpdef ['=' test])* [',']
  1130.  *
  1131.  */
  1132. static int
  1133. validate_varargslist(node *tree)
  1134. {
  1135.     int nch = NCH(tree);
  1136.     int res = validate_ntype(tree, varargslist) && (nch != 0);
  1137.  
  1138.     if (res && (nch >= 2) && (TYPE(CHILD(tree, nch - 1)) == NAME)) {
  1139.         /*  (fpdef ['=' test] ',')*
  1140.          *  ('*' NAME [',' '*' '*' NAME] | '*' '*' NAME)
  1141.          */
  1142.         int pos = 0;
  1143.         int remaining = nch;
  1144.  
  1145.         while (res && (TYPE(CHILD(tree, pos)) == fpdef)) {
  1146.             res = validate_fpdef(CHILD(tree, pos));
  1147.             if (res) {
  1148.                 if (TYPE(CHILD(tree, pos + 1)) == EQUAL) {
  1149.                     res = validate_test(CHILD(tree, pos + 2));
  1150.                     pos += 2;
  1151.                 }
  1152.                 res = res && validate_comma(CHILD(tree, pos + 1));
  1153.                 pos += 2;
  1154.             }
  1155.         }
  1156.         if (res) {
  1157.             remaining = nch - pos;
  1158.             res = ((remaining == 2) || (remaining == 3)
  1159.                    || (remaining == 5) || (remaining == 6));
  1160.             if (!res)
  1161.                 (void) validate_numnodes(tree, 2, "varargslist");
  1162.             else if (TYPE(CHILD(tree, pos)) == DOUBLESTAR)
  1163.                 return ((remaining == 2)
  1164.                         && validate_ntype(CHILD(tree, pos+1), NAME));
  1165.             else {
  1166.                 res = validate_star(CHILD(tree, pos++));
  1167.                 --remaining;
  1168.             }
  1169.         }
  1170.         if (res) {
  1171.             if (remaining == 2) {
  1172.                 res = (validate_star(CHILD(tree, pos))
  1173.                        && validate_ntype(CHILD(tree, pos + 1), NAME));
  1174.             }
  1175.             else {
  1176.                 res = validate_ntype(CHILD(tree, pos++), NAME);
  1177.                 if (res && (remaining >= 4)) {
  1178.                     res = validate_comma(CHILD(tree, pos));
  1179.                     if (--remaining == 3)
  1180.                         res = (validate_star(CHILD(tree, pos + 1))
  1181.                                && validate_star(CHILD(tree, pos + 2)));
  1182.                     else
  1183.                         res = validate_ntype(CHILD(tree, pos + 1), DOUBLESTAR);
  1184.                 }
  1185.             }
  1186.         }
  1187.         if (!res && !PyErr_Occurred())
  1188.             err_string("Incorrect validation of variable arguments list.");
  1189.     }
  1190.     else if (res) {
  1191.         /*  fpdef ['=' test] (',' fpdef ['=' test])* [',']  */
  1192.         if (TYPE(CHILD(tree, nch - 1)) == COMMA)
  1193.             --nch;
  1194.  
  1195.         /*  fpdef ['=' test] (',' fpdef ['=' test])*  */
  1196.         res = (is_odd(nch)
  1197.                && validate_fpdef(CHILD(tree, 0)));
  1198.  
  1199.         if (res && (nch > 1)) {
  1200.             int pos = 1;
  1201.             if (TYPE(CHILD(tree, 1)) == EQUAL) {
  1202.                 res = validate_test(CHILD(tree, 2));
  1203.                 pos += 2;
  1204.             }
  1205.             /*  ... (',' fpdef ['=' test])*  */
  1206.             for ( ; res && (pos < nch); pos += 2) {
  1207.                 /* ',' fpdef */
  1208.                 res = (validate_comma(CHILD(tree, pos))
  1209.                        && validate_fpdef(CHILD(tree, pos + 1)));
  1210.                 if (res
  1211.                     && ((nch - pos) > 2)
  1212.                     && (TYPE(CHILD(tree, pos + 2)) == EQUAL)) {
  1213.                     /* ['=' test] */
  1214.                     res = validate_test(CHILD(tree, pos + 3));
  1215.                     pos += 2;
  1216.                 }
  1217.             }
  1218.         }
  1219.     }
  1220.     else {
  1221.         err_string("Improperly formed argument list.");
  1222.     }
  1223.     return (res);
  1224. }
  1225.  
  1226.  
  1227. /*  VALIDATE(fpdef)
  1228.  *
  1229.  *  fpdef:
  1230.  *      NAME
  1231.  *    | '(' fplist ')'
  1232.  */
  1233. static int
  1234. validate_fpdef(node *tree)
  1235. {
  1236.     int nch = NCH(tree);
  1237.     int res = validate_ntype(tree, fpdef);
  1238.  
  1239.     if (res) {
  1240.         if (nch == 1)
  1241.             res = validate_ntype(CHILD(tree, 0), NAME);
  1242.         else if (nch == 3)
  1243.             res = (validate_lparen(CHILD(tree, 0))
  1244.                    && validate_fplist(CHILD(tree, 1))
  1245.                    && validate_rparen(CHILD(tree, 2)));
  1246.         else
  1247.             res = validate_numnodes(tree, 1, "fpdef");
  1248.     }
  1249.     return (res);
  1250. }
  1251.  
  1252.  
  1253. static int
  1254. validate_fplist(node *tree)
  1255. {
  1256.     return (validate_repeating_list(tree, fplist,
  1257.                                     validate_fpdef, "fplist"));
  1258. }
  1259.  
  1260.  
  1261. /*  simple_stmt | compound_stmt
  1262.  *
  1263.  */
  1264. static int
  1265. validate_stmt(node *tree)
  1266. {
  1267.     int res = (validate_ntype(tree, stmt)
  1268.                && validate_numnodes(tree, 1, "stmt"));
  1269.  
  1270.     if (res) {
  1271.         tree = CHILD(tree, 0);
  1272.  
  1273.         if (TYPE(tree) == simple_stmt)
  1274.             res = validate_simple_stmt(tree);
  1275.         else
  1276.             res = validate_compound_stmt(tree);
  1277.     }
  1278.     return (res);
  1279. }
  1280.  
  1281.  
  1282. /*  small_stmt (';' small_stmt)* [';'] NEWLINE
  1283.  *
  1284.  */
  1285. static int
  1286. validate_simple_stmt(node *tree)
  1287. {
  1288.     int nch = NCH(tree);
  1289.     int res = (validate_ntype(tree, simple_stmt)
  1290.                && (nch >= 2)
  1291.                && validate_small_stmt(CHILD(tree, 0))
  1292.                && validate_newline(CHILD(tree, nch - 1)));
  1293.  
  1294.     if (nch < 2)
  1295.         res = validate_numnodes(tree, 2, "simple_stmt");
  1296.     --nch;                              /* forget the NEWLINE    */
  1297.     if (res && is_even(nch))
  1298.         res = validate_semi(CHILD(tree, --nch));
  1299.     if (res && (nch > 2)) {
  1300.         int i;
  1301.  
  1302.         for (i = 1; res && (i < nch); i += 2)
  1303.             res = (validate_semi(CHILD(tree, i))
  1304.                    && validate_small_stmt(CHILD(tree, i + 1)));
  1305.     }
  1306.     return (res);
  1307. }
  1308.  
  1309.  
  1310. static int
  1311. validate_small_stmt(node *tree)
  1312. {
  1313.     int nch = NCH(tree);
  1314.     int res = (validate_numnodes(tree, 1, "small_stmt")
  1315.                && ((TYPE(CHILD(tree, 0)) == expr_stmt)
  1316.                    || (TYPE(CHILD(tree, 0)) == print_stmt)
  1317.                    || (TYPE(CHILD(tree, 0)) == del_stmt)
  1318.                    || (TYPE(CHILD(tree, 0)) == pass_stmt)
  1319.                    || (TYPE(CHILD(tree, 0)) == flow_stmt)
  1320.                    || (TYPE(CHILD(tree, 0)) == import_stmt)
  1321.                    || (TYPE(CHILD(tree, 0)) == global_stmt)
  1322.                    || (TYPE(CHILD(tree, 0)) == assert_stmt)
  1323.                    || (TYPE(CHILD(tree, 0)) == exec_stmt)));
  1324.  
  1325.     if (res)
  1326.         res = validate_node(CHILD(tree, 0));
  1327.     else if (nch == 1) {
  1328.         char buffer[60];
  1329.         (void) sprintf(buffer, "Unrecognized child node of small_stmt: %d.",
  1330.                        TYPE(CHILD(tree, 0)));
  1331.         err_string(buffer);
  1332.     }
  1333.     return (res);
  1334. }
  1335.  
  1336.  
  1337. /*  compound_stmt:
  1338.  *      if_stmt | while_stmt | for_stmt | try_stmt | funcdef | classdef
  1339.  */
  1340. static int
  1341. validate_compound_stmt(node *tree)
  1342. {
  1343.     int res = (validate_ntype(tree, compound_stmt)
  1344.                && validate_numnodes(tree, 1, "compound_stmt"));
  1345.  
  1346.     if (!res)
  1347.         return (0);
  1348.  
  1349.     tree = CHILD(tree, 0);
  1350.     res = ((TYPE(tree) == if_stmt)
  1351.            || (TYPE(tree) == while_stmt)
  1352.            || (TYPE(tree) == for_stmt)
  1353.            || (TYPE(tree) == try_stmt)
  1354.            || (TYPE(tree) == funcdef)
  1355.            || (TYPE(tree) == classdef));
  1356.     if (res)
  1357.         res = validate_node(tree);
  1358.     else {
  1359.         char buffer[60];
  1360.         (void) sprintf(buffer, "Illegal compound statement type: %d.",
  1361.                        TYPE(tree));
  1362.         err_string(buffer);
  1363.     }
  1364.     return (res);
  1365. }
  1366.  
  1367.  
  1368. static int
  1369. validate_expr_stmt(node *tree)
  1370. {
  1371.     int j;
  1372.     int nch = NCH(tree);
  1373.     int res = (validate_ntype(tree, expr_stmt)
  1374.                && is_odd(nch)
  1375.                && validate_testlist(CHILD(tree, 0)));
  1376.  
  1377.     for (j = 1; res && (j < nch); j += 2)
  1378.         res = (validate_equal(CHILD(tree, j))
  1379.                && validate_testlist(CHILD(tree, j + 1)));
  1380.  
  1381.     return (res);
  1382. }
  1383.  
  1384.  
  1385. /*  print_stmt:
  1386.  *
  1387.  *      'print' (test ',')* [test]
  1388.  *
  1389.  */
  1390. static int
  1391. validate_print_stmt(node *tree)
  1392. {
  1393.     int j;
  1394.     int nch = NCH(tree);
  1395.     int res = (validate_ntype(tree, print_stmt)
  1396.                && (nch != 0)
  1397.                && validate_name(CHILD(tree, 0), "print"));
  1398.  
  1399.     if (res && is_even(nch)) {
  1400.         res = validate_test(CHILD(tree, nch - 1));
  1401.         --nch;
  1402.     }
  1403.     else if (!res && !PyErr_Occurred())
  1404.         (void) validate_numnodes(tree, 1, "print_stmt");
  1405.     for (j = 1; res && (j < nch); j += 2)
  1406.         res = (validate_test(CHILD(tree, j))
  1407.                && validate_ntype(CHILD(tree, j + 1), COMMA));
  1408.  
  1409.     return (res);
  1410. }
  1411.  
  1412.  
  1413. static int
  1414. validate_del_stmt(node *tree)
  1415. {
  1416.     return (validate_numnodes(tree, 2, "del_stmt")
  1417.             && validate_name(CHILD(tree, 0), "del")
  1418.             && validate_exprlist(CHILD(tree, 1)));
  1419. }
  1420.  
  1421.  
  1422. static int
  1423. validate_return_stmt(node *tree)
  1424. {
  1425.     int nch = NCH(tree);
  1426.     int res = (validate_ntype(tree, return_stmt)
  1427.                && ((nch == 1) || (nch == 2))
  1428.                && validate_name(CHILD(tree, 0), "return"));
  1429.  
  1430.     if (res && (nch == 2))
  1431.         res = validate_testlist(CHILD(tree, 1));
  1432.  
  1433.     return (res);
  1434. }
  1435.  
  1436.  
  1437. static int
  1438. validate_raise_stmt(node *tree)
  1439. {
  1440.     int nch = NCH(tree);
  1441.     int res = (validate_ntype(tree, raise_stmt)
  1442.                && ((nch == 1) || (nch == 2) || (nch == 4) || (nch == 6)));
  1443.  
  1444.     if (res) {
  1445.         res = validate_name(CHILD(tree, 0), "raise");
  1446.         if (res && (nch >= 2))
  1447.             res = validate_test(CHILD(tree, 1));
  1448.         if (res && nch > 2) {
  1449.             res = (validate_comma(CHILD(tree, 2))
  1450.                    && validate_test(CHILD(tree, 3)));
  1451.             if (res && (nch > 4))
  1452.                 res = (validate_comma(CHILD(tree, 4))
  1453.                        && validate_test(CHILD(tree, 5)));
  1454.         }
  1455.     }
  1456.     else
  1457.         (void) validate_numnodes(tree, 2, "raise");
  1458.     if (res && (nch == 4))
  1459.         res = (validate_comma(CHILD(tree, 2))
  1460.                && validate_test(CHILD(tree, 3)));
  1461.  
  1462.     return (res);
  1463. }
  1464.  
  1465.  
  1466. /*  import_stmt:
  1467.  *
  1468.  *    'import' dotted_name (',' dotted_name)*
  1469.  *  | 'from' dotted_name 'import' ('*' | NAME (',' NAME)*)
  1470.  */
  1471. static int
  1472. validate_import_stmt(node *tree)
  1473. {
  1474.     int nch = NCH(tree);
  1475.     int res = (validate_ntype(tree, import_stmt)
  1476.                && (nch >= 2) && is_even(nch)
  1477.                && validate_ntype(CHILD(tree, 0), NAME)
  1478.                && validate_ntype(CHILD(tree, 1), dotted_name));
  1479.  
  1480.     if (res && (strcmp(STR(CHILD(tree, 0)), "import") == 0)) {
  1481.         int j;
  1482.  
  1483.         for (j = 2; res && (j < nch); j += 2)
  1484.             res = (validate_comma(CHILD(tree, j))
  1485.                    && validate_ntype(CHILD(tree, j + 1), dotted_name));
  1486.     }
  1487.     else if (res && validate_name(CHILD(tree, 0), "from")) {
  1488.         res = ((nch >= 4) && is_even(nch)
  1489.                && validate_name(CHILD(tree, 2), "import"));
  1490.         if (nch == 4) {
  1491.             res = ((TYPE(CHILD(tree, 3)) == NAME)
  1492.                    || (TYPE(CHILD(tree, 3)) == STAR));
  1493.             if (!res)
  1494.                 err_string("Illegal import statement.");
  1495.         }
  1496.         else {
  1497.             /*  'from' NAME 'import' NAME (',' NAME)+  */
  1498.             int j;
  1499.             res = validate_ntype(CHILD(tree, 3), NAME);
  1500.             for (j = 4; res && (j < nch); j += 2)
  1501.                 res = (validate_comma(CHILD(tree, j))
  1502.                        && validate_ntype(CHILD(tree, j + 1), NAME));
  1503.         }
  1504.     }
  1505.     else
  1506.         res = 0;
  1507.  
  1508.     return (res);
  1509. }
  1510.  
  1511.  
  1512. static int
  1513. validate_global_stmt(node *tree)
  1514. {
  1515.     int j;
  1516.     int nch = NCH(tree);
  1517.     int res = (validate_ntype(tree, global_stmt)
  1518.                && is_even(nch) && (nch >= 2));
  1519.  
  1520.     if (res)
  1521.         res = (validate_name(CHILD(tree, 0), "global")
  1522.                && validate_ntype(CHILD(tree, 1), NAME));
  1523.     for (j = 2; res && (j < nch); j += 2)
  1524.         res = (validate_comma(CHILD(tree, j))
  1525.                && validate_ntype(CHILD(tree, j + 1), NAME));
  1526.  
  1527.     return (res);
  1528. }
  1529.  
  1530.  
  1531. /*  exec_stmt:
  1532.  *
  1533.  *  'exec' expr ['in' test [',' test]]
  1534.  */
  1535. static int
  1536. validate_exec_stmt(node *tree)
  1537. {
  1538.     int nch = NCH(tree);
  1539.     int res = (validate_ntype(tree, exec_stmt)
  1540.                && ((nch == 2) || (nch == 4) || (nch == 6))
  1541.                && validate_name(CHILD(tree, 0), "exec")
  1542.                && validate_expr(CHILD(tree, 1)));
  1543.  
  1544.     if (!res && !PyErr_Occurred())
  1545.         err_string("Illegal exec statement.");
  1546.     if (res && (nch > 2))
  1547.         res = (validate_name(CHILD(tree, 2), "in")
  1548.                && validate_test(CHILD(tree, 3)));
  1549.     if (res && (nch == 6))
  1550.         res = (validate_comma(CHILD(tree, 4))
  1551.                && validate_test(CHILD(tree, 5)));
  1552.  
  1553.     return (res);
  1554. }
  1555.  
  1556.  
  1557. /*  assert_stmt:
  1558.  *
  1559.  *  'assert' test [',' test]
  1560.  */
  1561. static int
  1562. validate_assert_stmt(node *tree)
  1563. {
  1564.     int nch = NCH(tree);
  1565.     int res = (validate_ntype(tree, assert_stmt)
  1566.                && ((nch == 2) || (nch == 4))
  1567.                && (validate_name(CHILD(tree, 0), "__assert__") ||
  1568.                    validate_name(CHILD(tree, 0), "assert"))
  1569.                && validate_test(CHILD(tree, 1)));
  1570.  
  1571.     if (!res && !PyErr_Occurred())
  1572.         err_string("Illegal assert statement.");
  1573.     if (res && (nch > 2))
  1574.         res = (validate_comma(CHILD(tree, 2))
  1575.                && validate_test(CHILD(tree, 3)));
  1576.  
  1577.     return (res);
  1578. }
  1579.  
  1580.  
  1581. static int
  1582. validate_while(node *tree)
  1583. {
  1584.     int nch = NCH(tree);
  1585.     int res = (validate_ntype(tree, while_stmt)
  1586.                && ((nch == 4) || (nch == 7))
  1587.                && validate_name(CHILD(tree, 0), "while")
  1588.                && validate_test(CHILD(tree, 1))
  1589.                && validate_colon(CHILD(tree, 2))
  1590.                && validate_suite(CHILD(tree, 3)));
  1591.  
  1592.     if (res && (nch == 7))
  1593.         res = (validate_name(CHILD(tree, 4), "else")
  1594.                && validate_colon(CHILD(tree, 5))
  1595.                && validate_suite(CHILD(tree, 6)));
  1596.  
  1597.     return (res);
  1598. }
  1599.  
  1600.  
  1601. static int
  1602. validate_for(node *tree)
  1603. {
  1604.     int nch = NCH(tree);
  1605.     int res = (validate_ntype(tree, for_stmt)
  1606.                && ((nch == 6) || (nch == 9))
  1607.                && validate_name(CHILD(tree, 0), "for")
  1608.                && validate_exprlist(CHILD(tree, 1))
  1609.                && validate_name(CHILD(tree, 2), "in")
  1610.                && validate_testlist(CHILD(tree, 3))
  1611.                && validate_colon(CHILD(tree, 4))
  1612.                && validate_suite(CHILD(tree, 5)));
  1613.  
  1614.     if (res && (nch == 9))
  1615.         res = (validate_name(CHILD(tree, 6), "else")
  1616.                && validate_colon(CHILD(tree, 7))
  1617.                && validate_suite(CHILD(tree, 8)));
  1618.  
  1619.     return (res);
  1620. }
  1621.  
  1622.  
  1623. /*  try_stmt:
  1624.  *      'try' ':' suite (except_clause ':' suite)+ ['else' ':' suite]
  1625.  *    | 'try' ':' suite 'finally' ':' suite
  1626.  *
  1627.  */
  1628. static int
  1629. validate_try(tree)
  1630.     node *tree;
  1631. {
  1632.     int nch = NCH(tree);
  1633.     int pos = 3;
  1634.     int res = (validate_ntype(tree, try_stmt)
  1635.                && (nch >= 6) && ((nch % 3) == 0));
  1636.  
  1637.     if (res)
  1638.         res = (validate_name(CHILD(tree, 0), "try")
  1639.                && validate_colon(CHILD(tree, 1))
  1640.                && validate_suite(CHILD(tree, 2))
  1641.                && validate_colon(CHILD(tree, nch - 2))
  1642.                && validate_suite(CHILD(tree, nch - 1)));
  1643.     else {
  1644.         const char* name = "execpt";
  1645.         char buffer[60];
  1646.         if (TYPE(CHILD(tree, nch - 3)) != except_clause)
  1647.             name = STR(CHILD(tree, nch - 3));
  1648.         (void) sprintf(buffer,
  1649.                        "Illegal number of children for try/%s node.", name);
  1650.         err_string(buffer);
  1651.     }
  1652.     /*  Skip past except_clause sections:  */
  1653.     while (res && (TYPE(CHILD(tree, pos)) == except_clause)) {
  1654.         res = (validate_except_clause(CHILD(tree, pos))
  1655.                && validate_colon(CHILD(tree, pos + 1))
  1656.                && validate_suite(CHILD(tree, pos + 2)));
  1657.         pos += 3;
  1658.     }
  1659.     if (res && (pos < nch)) {
  1660.         res = validate_ntype(CHILD(tree, pos), NAME);
  1661.         if (res && (strcmp(STR(CHILD(tree, pos)), "finally") == 0))
  1662.             res = (validate_numnodes(tree, 6, "try/finally")
  1663.                    && validate_colon(CHILD(tree, 4))
  1664.                    && validate_suite(CHILD(tree, 5)));
  1665.         else if (res) {
  1666.             if (nch == (pos + 3)) {
  1667.                 res = ((strcmp(STR(CHILD(tree, pos)), "except") == 0)
  1668.                        || (strcmp(STR(CHILD(tree, pos)), "else") == 0));
  1669.                 if (!res)
  1670.                     err_string("Illegal trailing triple in try statement.");
  1671.             }
  1672.             else if (nch == (pos + 6)) {
  1673.                 res = (validate_name(CHILD(tree, pos), "except")
  1674.                        && validate_colon(CHILD(tree, pos + 1))
  1675.                        && validate_suite(CHILD(tree, pos + 2))
  1676.                        && validate_name(CHILD(tree, pos + 3), "else"));
  1677.             }
  1678.             else
  1679.                 res = validate_numnodes(tree, pos + 3, "try/except");
  1680.         }
  1681.     }
  1682.     return (res);
  1683. }
  1684.  
  1685.  
  1686. static int
  1687. validate_except_clause(node *tree)
  1688. {
  1689.     int nch = NCH(tree);
  1690.     int res = (validate_ntype(tree, except_clause)
  1691.                && ((nch == 1) || (nch == 2) || (nch == 4))
  1692.                && validate_name(CHILD(tree, 0), "except"));
  1693.  
  1694.     if (res && (nch > 1))
  1695.         res = validate_test(CHILD(tree, 1));
  1696.     if (res && (nch == 4))
  1697.         res = (validate_comma(CHILD(tree, 2))
  1698.                && validate_test(CHILD(tree, 3)));
  1699.  
  1700.     return (res);
  1701. }
  1702.  
  1703.  
  1704. static int
  1705. validate_test(node *tree)
  1706. {
  1707.     int nch = NCH(tree);
  1708.     int res = validate_ntype(tree, test) && is_odd(nch);
  1709.  
  1710.     if (res && (TYPE(CHILD(tree, 0)) == lambdef))
  1711.         res = ((nch == 1)
  1712.                && validate_lambdef(CHILD(tree, 0)));
  1713.     else if (res) {
  1714.         int pos;
  1715.         res = validate_and_test(CHILD(tree, 0));
  1716.         for (pos = 1; res && (pos < nch); pos += 2)
  1717.             res = (validate_name(CHILD(tree, pos), "or")
  1718.                    && validate_and_test(CHILD(tree, pos + 1)));
  1719.     }
  1720.     return (res);
  1721. }
  1722.  
  1723.  
  1724. static int
  1725. validate_and_test(node *tree)
  1726. {
  1727.     int pos;
  1728.     int nch = NCH(tree);
  1729.     int res = (validate_ntype(tree, and_test)
  1730.                && is_odd(nch)
  1731.                && validate_not_test(CHILD(tree, 0)));
  1732.  
  1733.     for (pos = 1; res && (pos < nch); pos += 2)
  1734.         res = (validate_name(CHILD(tree, pos), "and")
  1735.                && validate_not_test(CHILD(tree, 0)));
  1736.  
  1737.     return (res);
  1738. }
  1739.  
  1740.  
  1741. static int
  1742. validate_not_test(node *tree)
  1743. {
  1744.     int nch = NCH(tree);
  1745.     int res = validate_ntype(tree, not_test) && ((nch == 1) || (nch == 2));
  1746.  
  1747.     if (res) {
  1748.         if (nch == 2)
  1749.             res = (validate_name(CHILD(tree, 0), "not")
  1750.                    && validate_not_test(CHILD(tree, 1)));
  1751.         else if (nch == 1)
  1752.             res = validate_comparison(CHILD(tree, 0));
  1753.     }
  1754.     return (res);
  1755. }
  1756.  
  1757.  
  1758. static int
  1759. validate_comparison(node *tree)
  1760. {
  1761.     int pos;
  1762.     int nch = NCH(tree);
  1763.     int res = (validate_ntype(tree, comparison)
  1764.                && is_odd(nch)
  1765.                && validate_expr(CHILD(tree, 0)));
  1766.  
  1767.     for (pos = 1; res && (pos < nch); pos += 2)
  1768.         res = (validate_comp_op(CHILD(tree, pos))
  1769.                && validate_expr(CHILD(tree, pos + 1)));
  1770.  
  1771.     return (res);
  1772. }
  1773.  
  1774.  
  1775. static int
  1776. validate_comp_op(node *tree)
  1777. {
  1778.     int res = 0;
  1779.     int nch = NCH(tree);
  1780.  
  1781.     if (!validate_ntype(tree, comp_op))
  1782.         return (0);
  1783.     if (nch == 1) {
  1784.         /*
  1785.          *  Only child will be a terminal with a well-defined symbolic name
  1786.          *  or a NAME with a string of either 'is' or 'in'
  1787.          */
  1788.         tree = CHILD(tree, 0);
  1789.         switch (TYPE(tree)) {
  1790.             case LESS:
  1791.             case GREATER:
  1792.             case EQEQUAL:
  1793.             case EQUAL:
  1794.             case LESSEQUAL:
  1795.             case GREATEREQUAL:
  1796.             case NOTEQUAL:
  1797.               res = 1;
  1798.               break;
  1799.             case NAME:
  1800.               res = ((strcmp(STR(tree), "in") == 0)
  1801.                      || (strcmp(STR(tree), "is") == 0));
  1802.               if (!res) {
  1803.                   char buff[128];
  1804.                   (void) sprintf(buff, "Illegal operator: '%s'.", STR(tree));
  1805.                   err_string(buff);
  1806.               }
  1807.               break;
  1808.           default:
  1809.               err_string("Illegal comparison operator type.");
  1810.               break;
  1811.         }
  1812.     }
  1813.     else if ((res = validate_numnodes(tree, 2, "comp_op")) != 0) {
  1814.         res = (validate_ntype(CHILD(tree, 0), NAME)
  1815.                && validate_ntype(CHILD(tree, 1), NAME)
  1816.                && (((strcmp(STR(CHILD(tree, 0)), "is") == 0)
  1817.                     && (strcmp(STR(CHILD(tree, 1)), "not") == 0))
  1818.                    || ((strcmp(STR(CHILD(tree, 0)), "not") == 0)
  1819.                        && (strcmp(STR(CHILD(tree, 1)), "in") == 0))));
  1820.         if (!res && !PyErr_Occurred())
  1821.             err_string("Unknown comparison operator.");
  1822.     }
  1823.     return (res);
  1824. }
  1825.  
  1826.  
  1827. static int
  1828. validate_expr(node *tree)
  1829. {
  1830.     int j;
  1831.     int nch = NCH(tree);
  1832.     int res = (validate_ntype(tree, expr)
  1833.                && is_odd(nch)
  1834.                && validate_xor_expr(CHILD(tree, 0)));
  1835.  
  1836.     for (j = 2; res && (j < nch); j += 2)
  1837.         res = (validate_xor_expr(CHILD(tree, j))
  1838.                && validate_vbar(CHILD(tree, j - 1)));
  1839.  
  1840.     return (res);
  1841. }
  1842.  
  1843.  
  1844. static int
  1845. validate_xor_expr(node *tree)
  1846. {
  1847.     int j;
  1848.     int nch = NCH(tree);
  1849.     int res = (validate_ntype(tree, xor_expr)
  1850.                && is_odd(nch)
  1851.                && validate_and_expr(CHILD(tree, 0)));
  1852.  
  1853.     for (j = 2; res && (j < nch); j += 2)
  1854.         res = (validate_circumflex(CHILD(tree, j - 1))
  1855.                && validate_and_expr(CHILD(tree, j)));
  1856.  
  1857.     return (res);
  1858. }
  1859.  
  1860.  
  1861. static int
  1862. validate_and_expr(node *tree)
  1863. {
  1864.     int pos;
  1865.     int nch = NCH(tree);
  1866.     int res = (validate_ntype(tree, and_expr)
  1867.                && is_odd(nch)
  1868.                && validate_shift_expr(CHILD(tree, 0)));
  1869.  
  1870.     for (pos = 1; res && (pos < nch); pos += 2)
  1871.         res = (validate_ampersand(CHILD(tree, pos))
  1872.                && validate_shift_expr(CHILD(tree, pos + 1)));
  1873.  
  1874.     return (res);
  1875. }
  1876.  
  1877.  
  1878. static int
  1879. validate_chain_two_ops(tree, termvalid, op1, op2)
  1880.      node *tree;
  1881.      int (*termvalid)();
  1882.      int op1;
  1883.      int op2;
  1884.  {
  1885.     int pos = 1;
  1886.     int nch = NCH(tree);
  1887.     int res = (is_odd(nch)
  1888.                && (*termvalid)(CHILD(tree, 0)));
  1889.  
  1890.     for ( ; res && (pos < nch); pos += 2) {
  1891.         if (TYPE(CHILD(tree, pos)) != op1)
  1892.             res = validate_ntype(CHILD(tree, pos), op2);
  1893.         if (res)
  1894.             res = (*termvalid)(CHILD(tree, pos + 1));
  1895.     }
  1896.     return (res);
  1897. }
  1898.  
  1899.  
  1900. static int
  1901. validate_shift_expr(node *tree)
  1902. {
  1903.     return (validate_ntype(tree, shift_expr)
  1904.             && validate_chain_two_ops(tree, validate_arith_expr,
  1905.                                       LEFTSHIFT, RIGHTSHIFT));
  1906. }
  1907.  
  1908.  
  1909. static int
  1910. validate_arith_expr(node *tree)
  1911. {
  1912.     return (validate_ntype(tree, arith_expr)
  1913.             && validate_chain_two_ops(tree, validate_term, PLUS, MINUS));
  1914. }
  1915.  
  1916.  
  1917. static int
  1918. validate_term(node *tree)
  1919. {
  1920.     int pos = 1;
  1921.     int nch = NCH(tree);
  1922.     int res = (validate_ntype(tree, term)
  1923.                && is_odd(nch)
  1924.                && validate_factor(CHILD(tree, 0)));
  1925.  
  1926.     for ( ; res && (pos < nch); pos += 2)
  1927.         res = (((TYPE(CHILD(tree, pos)) == STAR)
  1928.                || (TYPE(CHILD(tree, pos)) == SLASH)
  1929.                || (TYPE(CHILD(tree, pos)) == PERCENT))
  1930.                && validate_factor(CHILD(tree, pos + 1)));
  1931.  
  1932.     return (res);
  1933. }
  1934.  
  1935.  
  1936. /*  factor:
  1937.  *
  1938.  *  factor: ('+'|'-'|'~') factor | power
  1939.  */
  1940. static int
  1941. validate_factor(node *tree)
  1942. {
  1943.     int nch = NCH(tree);
  1944.     int res = (validate_ntype(tree, factor)
  1945.                && (((nch == 2)
  1946.                     && ((TYPE(CHILD(tree, 0)) == PLUS)
  1947.                         || (TYPE(CHILD(tree, 0)) == MINUS)
  1948.                         || (TYPE(CHILD(tree, 0)) == TILDE))
  1949.                     && validate_factor(CHILD(tree, 1)))
  1950.                    || ((nch == 1)
  1951.                        && validate_power(CHILD(tree, 0)))));
  1952.     return (res);
  1953. }
  1954.  
  1955.  
  1956. /*  power:
  1957.  *
  1958.  *  power: atom trailer* ('**' factor)*
  1959.  */
  1960. static int
  1961. validate_power(node *tree)
  1962. {
  1963.     int pos = 1;
  1964.     int nch = NCH(tree);
  1965.     int res = (validate_ntype(tree, power) && (nch >= 1)
  1966.                && validate_atom(CHILD(tree, 0)));
  1967.  
  1968.     while (res && (pos < nch) && (TYPE(CHILD(tree, pos)) == trailer))
  1969.         res = validate_trailer(CHILD(tree, pos++));
  1970.     if (res && (pos < nch)) {
  1971.         if (!is_even(nch - pos)) {
  1972.             err_string("Illegal number of nodes for 'power'.");
  1973.             return (0);
  1974.         }
  1975.         for ( ; res && (pos < (nch - 1)); pos += 2)
  1976.             res = (validate_doublestar(CHILD(tree, pos))
  1977.                    && validate_factor(CHILD(tree, pos + 1)));
  1978.     }
  1979.     return (res);
  1980. }
  1981.  
  1982.  
  1983. static int
  1984. validate_atom(node *tree)
  1985. {
  1986.     int pos;
  1987.     int nch = NCH(tree);
  1988.     int res = validate_ntype(tree, atom) && (nch >= 1);
  1989.  
  1990.     if (res) {
  1991.         switch (TYPE(CHILD(tree, 0))) {
  1992.           case LPAR:
  1993.             res = ((nch <= 3)
  1994.                    && (validate_rparen(CHILD(tree, nch - 1))));
  1995.  
  1996.             if (res && (nch == 3))
  1997.                 res = validate_testlist(CHILD(tree, 1));
  1998.             break;
  1999.           case LSQB:
  2000.             res = ((nch <= 3)
  2001.                    && validate_ntype(CHILD(tree, nch - 1), RSQB));
  2002.  
  2003.             if (res && (nch == 3))
  2004.                 res = validate_testlist(CHILD(tree, 1));
  2005.             break;
  2006.           case LBRACE:
  2007.             res = ((nch <= 3)
  2008.                    && validate_ntype(CHILD(tree, nch - 1), RBRACE));
  2009.  
  2010.             if (res && (nch == 3))
  2011.                 res = validate_dictmaker(CHILD(tree, 1));
  2012.             break;
  2013.           case BACKQUOTE:
  2014.             res = ((nch == 3)
  2015.                    && validate_testlist(CHILD(tree, 1))
  2016.                    && validate_ntype(CHILD(tree, 2), BACKQUOTE));
  2017.             break;
  2018.           case NAME:
  2019.           case NUMBER:
  2020.             res = (nch == 1);
  2021.             break;
  2022.           case STRING:
  2023.             for (pos = 1; res && (pos < nch); ++pos)
  2024.                 res = validate_ntype(CHILD(tree, pos), STRING);
  2025.             break;
  2026.           default:
  2027.             res = 0;
  2028.             break;
  2029.         }
  2030.     }
  2031.     return (res);
  2032. }
  2033.  
  2034.  
  2035. /*  funcdef:
  2036.  *      'def' NAME parameters ':' suite
  2037.  *
  2038.  */
  2039. static int
  2040. validate_funcdef(node *tree)
  2041. {
  2042.     return (validate_ntype(tree, funcdef)
  2043.             && validate_numnodes(tree, 5, "funcdef")
  2044.             && validate_name(CHILD(tree, 0), "def")
  2045.             && validate_ntype(CHILD(tree, 1), NAME)
  2046.             && validate_colon(CHILD(tree, 3))
  2047.             && validate_parameters(CHILD(tree, 2))
  2048.             && validate_suite(CHILD(tree, 4)));
  2049. }
  2050.  
  2051.  
  2052. static int
  2053. validate_lambdef(node *tree)
  2054. {
  2055.     int nch = NCH(tree);
  2056.     int res = (validate_ntype(tree, lambdef)
  2057.                && ((nch == 3) || (nch == 4))
  2058.                && validate_name(CHILD(tree, 0), "lambda")
  2059.                && validate_colon(CHILD(tree, nch - 2))
  2060.                && validate_test(CHILD(tree, nch - 1)));
  2061.  
  2062.     if (res && (nch == 4))
  2063.         res = validate_varargslist(CHILD(tree, 1));
  2064.     else if (!res && !PyErr_Occurred())
  2065.         (void) validate_numnodes(tree, 3, "lambdef");
  2066.  
  2067.     return (res);
  2068. }
  2069.  
  2070.  
  2071. /*  arglist:
  2072.  *
  2073.  *  (argument ',')* (argument* [','] | '*' test [',' '**' test] | '**' test)
  2074.  */
  2075. static int
  2076. validate_arglist(node *tree)
  2077. {
  2078.     int nch = NCH(tree);
  2079.     int i, ok;
  2080.     node *last;
  2081.  
  2082.     if (nch <= 0)
  2083.         /* raise the right error from having an invalid number of children */
  2084.         return validate_numnodes(tree, nch + 1, "arglist");
  2085.  
  2086.     last = CHILD(tree, nch - 1);
  2087.     if (TYPE(last) == test) {
  2088.         /* Extended call syntax introduced in Python 1.6 has been used;
  2089.          * validate and strip that off and continue;
  2090.          * adjust nch to perform the cut, and ensure resulting nch is even
  2091.          * (validation of the first part doesn't require that).
  2092.          */
  2093.         if (nch < 2) {
  2094.             validate_numnodes(tree, nch + 1, "arglist");
  2095.             return 0;
  2096.         }
  2097.         ok = validate_test(last);
  2098.         if (ok) {
  2099.             node *prev = CHILD(tree, nch - 2);
  2100.             /* next must be '*' or '**' */
  2101.             if (validate_doublestar(prev)) {
  2102.                 nch -= 2;
  2103.                 if (nch >= 3) {
  2104.                     /* may include:  '*' test ',' */
  2105.                     last = CHILD(tree, nch - 1);
  2106.                     prev = CHILD(tree, nch - 2);
  2107.                     if (TYPE(prev) == test) {
  2108.                         ok = validate_comma(last)
  2109.                              && validate_test(prev)
  2110.                              && validate_star(CHILD(tree, nch - 3));
  2111.                         if (ok)
  2112.                             nch -= 3;
  2113.                     }
  2114.                     /* otherwise, nothing special */
  2115.                 }
  2116.             }
  2117.             else {
  2118.                 /* must be only:  '*' test */
  2119.                 PyErr_Clear();
  2120.                 ok = validate_star(prev);
  2121.                 nch -= 2;
  2122.             }
  2123.             if (ok && is_odd(nch)) {
  2124.                 /* Illegal number of nodes before extended call syntax;
  2125.                  * validation of the "normal" arguments does not require
  2126.                  * a trailing comma, but requiring an even number of
  2127.                  * children will effect the same requirement.
  2128.                  */
  2129.                 return validate_numnodes(tree, nch + 1, "arglist");
  2130.             }
  2131.         }
  2132.     }
  2133.     /* what remains must be:  (argument ",")* [argument [","]] */
  2134.     i = 0;
  2135.     while (ok && nch - i >= 2) {
  2136.         ok = validate_argument(CHILD(tree, i))
  2137.              && validate_comma(CHILD(tree, i + 1));
  2138.         i += 2;
  2139.     }
  2140.     if (ok && i < nch) {
  2141.         ok = validate_comma(CHILD(tree, i));
  2142.         ++i;
  2143.     }
  2144.     if (i != nch) {
  2145.         /* internal error! */
  2146.         ok = 0;
  2147.         err_string("arglist: internal error; nch != i");
  2148.     }
  2149.     return (ok);
  2150. }
  2151.  
  2152.  
  2153.  
  2154. /*  argument:
  2155.  *
  2156.  *  [test '='] test
  2157.  */
  2158. static int
  2159. validate_argument(node *tree)
  2160. {
  2161.     int nch = NCH(tree);
  2162.     int res = (validate_ntype(tree, argument)
  2163.                && ((nch == 1) || (nch == 3))
  2164.                && validate_test(CHILD(tree, 0)));
  2165.  
  2166.     if (res && (nch == 3))
  2167.         res = (validate_equal(CHILD(tree, 1))
  2168.                && validate_test(CHILD(tree, 2)));
  2169.  
  2170.     return (res);
  2171. }
  2172.  
  2173.  
  2174.  
  2175. /*  trailer:
  2176.  *
  2177.  *  '(' [arglist] ')' | '[' subscriptlist ']' | '.' NAME
  2178.  */
  2179. static int
  2180. validate_trailer(node *tree)
  2181. {
  2182.     int nch = NCH(tree);
  2183.     int res = validate_ntype(tree, trailer) && ((nch == 2) || (nch == 3));
  2184.  
  2185.     if (res) {
  2186.         switch (TYPE(CHILD(tree, 0))) {
  2187.           case LPAR:
  2188.             res = validate_rparen(CHILD(tree, nch - 1));
  2189.             if (res && (nch == 3))
  2190.                 res = validate_arglist(CHILD(tree, 1));
  2191.             break;
  2192.           case LSQB:
  2193.             res = (validate_numnodes(tree, 3, "trailer")
  2194.                    && validate_subscriptlist(CHILD(tree, 1))
  2195.                    && validate_ntype(CHILD(tree, 2), RSQB));
  2196.             break;
  2197.           case DOT:
  2198.             res = (validate_numnodes(tree, 2, "trailer")
  2199.                    && validate_ntype(CHILD(tree, 1), NAME));
  2200.             break;
  2201.           default:
  2202.             res = 0;
  2203.             break;
  2204.         }
  2205.     }
  2206.     else {
  2207.         (void) validate_numnodes(tree, 2, "trailer");
  2208.     }
  2209.     return (res);
  2210. }
  2211.  
  2212.  
  2213. /*  subscriptlist:
  2214.  *
  2215.  *  subscript (',' subscript)* [',']
  2216.  */
  2217. static int
  2218. validate_subscriptlist(node *tree)
  2219. {
  2220.     return (validate_repeating_list(tree, subscriptlist,
  2221.                                     validate_subscript, "subscriptlist"));
  2222. }
  2223.  
  2224.  
  2225. /*  subscript:
  2226.  *
  2227.  *  '.' '.' '.' | test | [test] ':' [test] [sliceop]
  2228.  */
  2229. static int
  2230. validate_subscript(node *tree)
  2231. {
  2232.     int offset = 0;
  2233.     int nch = NCH(tree);
  2234.     int res = validate_ntype(tree, subscript) && (nch >= 1) && (nch <= 4);
  2235.  
  2236.     if (!res) {
  2237.         if (!PyErr_Occurred())
  2238.             err_string("invalid number of arguments for subscript node");
  2239.         return (0);
  2240.     }
  2241.     if (TYPE(CHILD(tree, 0)) == DOT)
  2242.         /* take care of ('.' '.' '.') possibility */
  2243.         return (validate_numnodes(tree, 3, "subscript")
  2244.                 && validate_dot(CHILD(tree, 0))
  2245.                 && validate_dot(CHILD(tree, 1))
  2246.                 && validate_dot(CHILD(tree, 2)));
  2247.     if (nch == 1) {
  2248.         if (TYPE(CHILD(tree, 0)) == test)
  2249.             res = validate_test(CHILD(tree, 0));
  2250.         else
  2251.             res = validate_colon(CHILD(tree, 0));
  2252.         return (res);
  2253.     }
  2254.     /*  Must be [test] ':' [test] [sliceop],
  2255.      *  but at least one of the optional components will
  2256.      *  be present, but we don't know which yet.
  2257.      */
  2258.     if ((TYPE(CHILD(tree, 0)) != COLON) || (nch == 4)) {
  2259.         res = validate_test(CHILD(tree, 0));
  2260.         offset = 1;
  2261.     }
  2262.     if (res)
  2263.         res = validate_colon(CHILD(tree, offset));
  2264.     if (res) {
  2265.         int rem = nch - ++offset;
  2266.         if (rem) {
  2267.             if (TYPE(CHILD(tree, offset)) == test) {
  2268.                 res = validate_test(CHILD(tree, offset));
  2269.                 ++offset;
  2270.                 --rem;
  2271.             }
  2272.             if (res && rem)
  2273.                 res = validate_sliceop(CHILD(tree, offset));
  2274.         }
  2275.     }
  2276.     return (res);
  2277. }
  2278.  
  2279.  
  2280. static int
  2281. validate_sliceop(node *tree)
  2282. {
  2283.     int nch = NCH(tree);
  2284.     int res = ((nch == 1) || validate_numnodes(tree, 2, "sliceop"))
  2285.               && validate_ntype(tree, sliceop);
  2286.     if (!res && !PyErr_Occurred()) {
  2287.         res = validate_numnodes(tree, 1, "sliceop");
  2288.     }
  2289.     if (res)
  2290.         res = validate_colon(CHILD(tree, 0));
  2291.     if (res && (nch == 2))
  2292.         res = validate_test(CHILD(tree, 1));
  2293.  
  2294.     return (res);
  2295. }
  2296.  
  2297.  
  2298. static int
  2299. validate_exprlist(node *tree)
  2300. {
  2301.     return (validate_repeating_list(tree, exprlist,
  2302.                                     validate_expr, "exprlist"));
  2303. }
  2304.  
  2305.  
  2306. static int
  2307. validate_dictmaker(node *tree)
  2308. {
  2309.     int nch = NCH(tree);
  2310.     int res = (validate_ntype(tree, dictmaker)
  2311.                && (nch >= 3)
  2312.                && validate_test(CHILD(tree, 0))
  2313.                && validate_colon(CHILD(tree, 1))
  2314.                && validate_test(CHILD(tree, 2)));
  2315.  
  2316.     if (res && ((nch % 4) == 0))
  2317.         res = validate_comma(CHILD(tree, --nch));
  2318.     else if (res)
  2319.         res = ((nch % 4) == 3);
  2320.  
  2321.     if (res && (nch > 3)) {
  2322.         int pos = 3;
  2323.         /*  ( ',' test ':' test )*  */
  2324.         while (res && (pos < nch)) {
  2325.             res = (validate_comma(CHILD(tree, pos))
  2326.                    && validate_test(CHILD(tree, pos + 1))
  2327.                    && validate_colon(CHILD(tree, pos + 2))
  2328.                    && validate_test(CHILD(tree, pos + 3)));
  2329.             pos += 4;
  2330.         }
  2331.     }
  2332.     return (res);
  2333. }
  2334.  
  2335.  
  2336. static int
  2337. validate_eval_input(node *tree)
  2338. {
  2339.     int pos;
  2340.     int nch = NCH(tree);
  2341.     int res = (validate_ntype(tree, eval_input)
  2342.                && (nch >= 2)
  2343.                && validate_testlist(CHILD(tree, 0))
  2344.                && validate_ntype(CHILD(tree, nch - 1), ENDMARKER));
  2345.  
  2346.     for (pos = 1; res && (pos < (nch - 1)); ++pos)
  2347.         res = validate_ntype(CHILD(tree, pos), NEWLINE);
  2348.  
  2349.     return (res);
  2350. }
  2351.  
  2352.  
  2353. static int
  2354. validate_node(node *tree)
  2355. {
  2356.     int   nch  = 0;                     /* num. children on current node  */
  2357.     int   res  = 1;                     /* result value                   */
  2358.     node* next = 0;                     /* node to process after this one */
  2359.  
  2360.     while (res & (tree != 0)) {
  2361.         nch  = NCH(tree);
  2362.         next = 0;
  2363.         switch (TYPE(tree)) {
  2364.             /*
  2365.              *  Definition nodes.
  2366.              */
  2367.           case funcdef:
  2368.             res = validate_funcdef(tree);
  2369.             break;
  2370.           case classdef:
  2371.             res = validate_class(tree);
  2372.             break;
  2373.             /*
  2374.              *  "Trivial" parse tree nodes.
  2375.              *  (Why did I call these trivial?)
  2376.              */
  2377.           case stmt:
  2378.             res = validate_stmt(tree);
  2379.             break;
  2380.           case small_stmt:
  2381.             /*
  2382.              *  expr_stmt | print_stmt  | del_stmt | pass_stmt | flow_stmt
  2383.              *  | import_stmt | global_stmt | exec_stmt | assert_stmt
  2384.              */
  2385.             res = validate_small_stmt(tree);
  2386.             break;
  2387.           case flow_stmt:
  2388.             res  = (validate_numnodes(tree, 1, "flow_stmt")
  2389.                     && ((TYPE(CHILD(tree, 0)) == break_stmt)
  2390.                         || (TYPE(CHILD(tree, 0)) == continue_stmt)
  2391.                         || (TYPE(CHILD(tree, 0)) == return_stmt)
  2392.                         || (TYPE(CHILD(tree, 0)) == raise_stmt)));
  2393.             if (res)
  2394.                 next = CHILD(tree, 0);
  2395.             else if (nch == 1)
  2396.                 err_string("Illegal flow_stmt type.");
  2397.             break;
  2398.             /*
  2399.              *  Compound statements.
  2400.              */
  2401.           case simple_stmt:
  2402.             res = validate_simple_stmt(tree);
  2403.             break;
  2404.           case compound_stmt:
  2405.             res = validate_compound_stmt(tree);
  2406.             break;
  2407.             /*
  2408.              *  Fundemental statements.
  2409.              */
  2410.           case expr_stmt:
  2411.             res = validate_expr_stmt(tree);
  2412.             break;
  2413.           case print_stmt:
  2414.             res = validate_print_stmt(tree);
  2415.             break;
  2416.           case del_stmt:
  2417.             res = validate_del_stmt(tree);
  2418.             break;
  2419.           case pass_stmt:
  2420.             res = (validate_numnodes(tree, 1, "pass")
  2421.                    && validate_name(CHILD(tree, 0), "pass"));
  2422.             break;
  2423.           case break_stmt:
  2424.             res = (validate_numnodes(tree, 1, "break")
  2425.                    && validate_name(CHILD(tree, 0), "break"));
  2426.             break;
  2427.           case continue_stmt:
  2428.             res = (validate_numnodes(tree, 1, "continue")
  2429.                    && validate_name(CHILD(tree, 0), "continue"));
  2430.             break;
  2431.           case return_stmt:
  2432.             res = validate_return_stmt(tree);
  2433.             break;
  2434.           case raise_stmt:
  2435.             res = validate_raise_stmt(tree);
  2436.             break;
  2437.           case import_stmt:
  2438.             res = validate_import_stmt(tree);
  2439.             break;
  2440.           case global_stmt:
  2441.             res = validate_global_stmt(tree);
  2442.             break;
  2443.           case exec_stmt:
  2444.             res = validate_exec_stmt(tree);
  2445.             break;
  2446.           case assert_stmt:
  2447.             res = validate_assert_stmt(tree);
  2448.             break;
  2449.           case if_stmt:
  2450.             res = validate_if(tree);
  2451.             break;
  2452.           case while_stmt:
  2453.             res = validate_while(tree);
  2454.             break;
  2455.           case for_stmt:
  2456.             res = validate_for(tree);
  2457.             break;
  2458.           case try_stmt:
  2459.             res = validate_try(tree);
  2460.             break;
  2461.           case suite:
  2462.             res = validate_suite(tree);
  2463.             break;
  2464.             /*
  2465.              *  Expression nodes.
  2466.              */
  2467.           case testlist:
  2468.             res = validate_testlist(tree);
  2469.             break;
  2470.           case test:
  2471.             res = validate_test(tree);
  2472.             break;
  2473.           case and_test:
  2474.             res = validate_and_test(tree);
  2475.             break;
  2476.           case not_test:
  2477.             res = validate_not_test(tree);
  2478.             break;
  2479.           case comparison:
  2480.             res = validate_comparison(tree);
  2481.             break;
  2482.           case exprlist:
  2483.             res = validate_exprlist(tree);
  2484.             break;
  2485.           case comp_op:
  2486.             res = validate_comp_op(tree);
  2487.             break;
  2488.           case expr:
  2489.             res = validate_expr(tree);
  2490.             break;
  2491.           case xor_expr:
  2492.             res = validate_xor_expr(tree);
  2493.             break;
  2494.           case and_expr:
  2495.             res = validate_and_expr(tree);
  2496.             break;
  2497.           case shift_expr:
  2498.             res = validate_shift_expr(tree);
  2499.             break;
  2500.           case arith_expr:
  2501.             res = validate_arith_expr(tree);
  2502.             break;
  2503.           case term:
  2504.             res = validate_term(tree);
  2505.             break;
  2506.           case factor:
  2507.             res = validate_factor(tree);
  2508.             break;
  2509.           case power:
  2510.             res = validate_power(tree);
  2511.             break;
  2512.           case atom:
  2513.             res = validate_atom(tree);
  2514.             break;
  2515.  
  2516.           default:
  2517.             /* Hopefully never reached! */
  2518.             err_string("Unrecogniged node type.");
  2519.             res = 0;
  2520.             break;
  2521.         }
  2522.         tree = next;
  2523.     }
  2524.     return (res);
  2525. }
  2526.  
  2527.  
  2528. static int
  2529. validate_expr_tree(node *tree)
  2530. {
  2531.     int res = validate_eval_input(tree);
  2532.  
  2533.     if (!res && !PyErr_Occurred())
  2534.         err_string("Could not validate expression tuple.");
  2535.  
  2536.     return (res);
  2537. }
  2538.  
  2539.  
  2540. /*  file_input:
  2541.  *      (NEWLINE | stmt)* ENDMARKER
  2542.  */
  2543. static int
  2544. validate_file_input(node *tree)
  2545. {
  2546.     int j   = 0;
  2547.     int nch = NCH(tree) - 1;
  2548.     int res = ((nch >= 0)
  2549.                && validate_ntype(CHILD(tree, nch), ENDMARKER));
  2550.  
  2551.     for ( ; res && (j < nch); ++j) {
  2552.         if (TYPE(CHILD(tree, j)) == stmt)
  2553.             res = validate_stmt(CHILD(tree, j));
  2554.         else
  2555.             res = validate_newline(CHILD(tree, j));
  2556.     }
  2557.     /*  This stays in to prevent any internal failues from getting to the
  2558.      *  user.  Hopefully, this won't be needed.  If a user reports getting
  2559.      *  this, we have some debugging to do.
  2560.      */
  2561.     if (!res && !PyErr_Occurred())
  2562.         err_string("VALIDATION FAILURE: report this to the maintainer!.");
  2563.  
  2564.     return (res);
  2565. }
  2566.  
  2567.  
  2568. static PyObject*
  2569. pickle_constructor = NULL;
  2570.  
  2571.  
  2572. static PyObject*
  2573. parser__pickler(PyObject *self, PyObject *args)
  2574. {
  2575.     NOTE(ARGUNUSED(self))
  2576.     PyObject *result = NULL;
  2577.     PyObject *ast = NULL;
  2578.     PyObject *empty_dict = NULL;
  2579.  
  2580.     if (PyArg_ParseTuple(args, "O!:_pickler", &PyAST_Type, &ast)) {
  2581.         PyObject *newargs;
  2582.         PyObject *tuple;
  2583.  
  2584.         if ((empty_dict = PyDict_New()) == NULL)
  2585.             goto finally;
  2586.         if ((newargs = Py_BuildValue("Oi", ast, 1)) == NULL)
  2587.             goto finally;
  2588.         tuple = parser_ast2tuple((PyAST_Object*)NULL, newargs, empty_dict);
  2589.         if (tuple != NULL) {
  2590.             result = Py_BuildValue("O(O)", pickle_constructor, tuple);
  2591.             Py_DECREF(tuple);
  2592.         }
  2593.         Py_DECREF(empty_dict);
  2594.         Py_DECREF(newargs);
  2595.     }
  2596.   finally:
  2597.     Py_XDECREF(empty_dict);
  2598.  
  2599.     return (result);
  2600. }
  2601.  
  2602.  
  2603. /*  Functions exported by this module.  Most of this should probably
  2604.  *  be converted into an AST object with methods, but that is better
  2605.  *  done directly in Python, allowing subclasses to be created directly.
  2606.  *  We'd really have to write a wrapper around it all anyway to allow
  2607.  *  inheritance.
  2608.  */
  2609. static PyMethodDef parser_functions[] =  {
  2610.     {"ast2tuple",       (PyCFunction)parser_ast2tuple,  PUBLIC_METHOD_TYPE,
  2611.         "Creates a tuple-tree representation of an AST."},
  2612.     {"ast2list",        (PyCFunction)parser_ast2list,   PUBLIC_METHOD_TYPE,
  2613.         "Creates a list-tree representation of an AST."},
  2614.     {"compileast",      (PyCFunction)parser_compileast, PUBLIC_METHOD_TYPE,
  2615.         "Compiles an AST object into a code object."},
  2616.     {"expr",            (PyCFunction)parser_expr,       PUBLIC_METHOD_TYPE,
  2617.         "Creates an AST object from an expression."},
  2618.     {"isexpr",          (PyCFunction)parser_isexpr,     PUBLIC_METHOD_TYPE,
  2619.         "Determines if an AST object was created from an expression."},
  2620.     {"issuite",         (PyCFunction)parser_issuite,    PUBLIC_METHOD_TYPE,
  2621.         "Determines if an AST object was created from a suite."},
  2622.     {"suite",           (PyCFunction)parser_suite,      PUBLIC_METHOD_TYPE,
  2623.         "Creates an AST object from a suite."},
  2624.     {"sequence2ast",    (PyCFunction)parser_tuple2ast,  PUBLIC_METHOD_TYPE,
  2625.         "Creates an AST object from a tree representation."},
  2626.     {"tuple2ast",       (PyCFunction)parser_tuple2ast,  PUBLIC_METHOD_TYPE,
  2627.         "Creates an AST object from a tree representation."},
  2628.  
  2629.     /* private stuff: support pickle module */
  2630.     {"_pickler",        (PyCFunction)parser__pickler,   METH_VARARGS,
  2631.         "Returns the pickle magic to allow ast objects to be pickled."},
  2632.  
  2633.     {NULL, NULL, 0, NULL}
  2634.     };
  2635.  
  2636.  
  2637. DL_EXPORT(void)
  2638. initparser()
  2639.  {
  2640.     PyObject* module;
  2641.     PyObject* dict;
  2642.         
  2643.     PyAST_Type.ob_type = &PyType_Type;
  2644.     module = Py_InitModule("parser", parser_functions);
  2645.     dict = PyModule_GetDict(module);
  2646.  
  2647.     if (parser_error == 0)
  2648.         parser_error = PyErr_NewException("parser.ParserError", NULL, NULL);
  2649.     else
  2650.         puts("parser module initialized more than once!");
  2651.  
  2652.     if ((parser_error == 0)
  2653.         || (PyDict_SetItemString(dict, "ParserError", parser_error) != 0)) {
  2654.         /*
  2655.          *  This is serious.
  2656.          */
  2657.         Py_FatalError("can't define parser.ParserError");
  2658.     }
  2659.     /*
  2660.      *  Nice to have, but don't cry if we fail.
  2661.      */
  2662.     Py_INCREF(&PyAST_Type);
  2663.     PyDict_SetItemString(dict, "ASTType", (PyObject*)&PyAST_Type);
  2664.  
  2665.     PyDict_SetItemString(dict, "__copyright__",
  2666.                          PyString_FromString(parser_copyright_string));
  2667.     PyDict_SetItemString(dict, "__doc__",
  2668.                          PyString_FromString(parser_doc_string));
  2669.     PyDict_SetItemString(dict, "__version__",
  2670.                          PyString_FromString(parser_version_string));
  2671.  
  2672.     /* register to support pickling */
  2673.     module = PyImport_ImportModule("copy_reg");
  2674.     if (module != NULL) {
  2675.         PyObject *func, *pickler;
  2676.  
  2677.         func = PyObject_GetAttrString(module, "pickle");
  2678.         pickle_constructor = PyDict_GetItemString(dict, "sequence2ast");
  2679.         pickler = PyDict_GetItemString(dict, "_pickler");
  2680.         Py_XINCREF(pickle_constructor);
  2681.         if ((func != NULL) && (pickle_constructor != NULL)
  2682.             && (pickler != NULL)) {
  2683.             PyObject *res;
  2684.  
  2685.             res = PyObject_CallFunction(
  2686.                     func, "OOO", &PyAST_Type, pickler, pickle_constructor);
  2687.             Py_XDECREF(res);
  2688.         }
  2689.         Py_XDECREF(func);
  2690.         Py_DECREF(module);
  2691.     }
  2692. }
  2693.